Submission #63804


ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
/* #region Head */
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using vll = vc<ll>;
using vvll = vvc<ll>;
using vld = vc<ld>;
using vvld = vvc<ld>;
using vs = vc<string>;
using vvs = vvc<string>;
template <class T, class U> using um = unordered_map<T, U>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqa = priority_queue<T, vc<T>, greater<T>>;
template <class T> using us = unordered_set<T>;
#define REP(i, m, n) for (ll i = (m), i##_len = (ll)(n); i < i##_len; ++(i))
#define REPM(i, m, n) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; ++(i))
#define REPR(i, m, n) for (ll i = (m), i##_min = (ll)(n); i >= i##_min; --(i))
#define REPD(i, m, n, d) for (ll i = (m), i##_len = (ll)(n); i < i##_len; i += (d))
#define REPMD(i, m, n, d) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; i += (d))
#define REPI(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define ALL(x) begin(x), end(x)
#define SIZE(x) ((ll)(x).size())
#define PERM(c) \
sort(ALL(c)); \
for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))
#define UNIQ(v) v.erase(unique(ALL(v)), v.end());
#define endl '\n'
#define sqrt sqrtl
#define floor floorl
#define log2 log2l
constexpr ll INF = 1'010'000'000'000'000'017LL;
constexpr ll MOD = 1'000'000'007LL; // 1e9 + 7
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.14159265358979323846;
template <typename T> istream &operator>>(istream &is, vc<T> &vec) { // vector 入力
for (T &x : vec) is >> x;
return is;
}
template <typename T> ostream &operator<<(ostream &os, vc<T> &vec) { // vector 出力 (for dump)
os << "{";
REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "" : ", ");
os << "}";
return os;
}
template <typename T> ostream &operator>>(ostream &os, vc<T> &vec) { // vector 出力 (inline)
REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "\n" : " ");
return os;
}
template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &pair_var) { // pair 入力
is >> pair_var.first >> pair_var.second;
return is;
}
template <typename T, typename U> ostream &operator<<(ostream &os, pair<T, U> &pair_var) { // pair 出力
os << "(" << pair_var.first << ", " << pair_var.second << ")";
return os;
}
// map, um, set, us 出力
template <class T> ostream &out_iter(ostream &os, T &map_var) {
os << "{";
REPI(itr, map_var) {
os << *itr;
auto itrcp = itr;
if (++itrcp != map_var.end()) os << ", ";
}
return os << "}";
}
template <typename T, typename U> ostream &operator<<(ostream &os, map<T, U> &map_var) { return out_iter(os, map_var); }
template <typename T, typename U> ostream &operator<<(ostream &os, um<T, U> &map_var) {
os << "{";
REPI(itr, map_var) {
auto [key, value] = *itr;
os << "(" << key << ", " << value << ")";
auto itrcp = itr;
if (++itrcp != map_var.end()) os << ", ";
}
os << "}";
return os;
}
template <typename T> ostream &operator<<(ostream &os, set<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, us<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, pq<T> &pq_var) {
pq<T> pq_cp(pq_var);
os << "{";
if (!pq_cp.empty()) {
os << pq_cp.top(), pq_cp.pop();
while (!pq_cp.empty()) os << ", " << pq_cp.top(), pq_cp.pop();
}
return os << "}";
}
// dump
#define DUMPOUT cerr
void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head &&head, Tail &&... tail) {
DUMPOUT << head;
if (sizeof...(Tail) > 0) DUMPOUT << ", ";
dump_func(move(tail)...);
}
// chmax (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmax(T &xmax, const U &x, Comp comp = {}) {
if (comp(xmax, x)) {
xmax = x;
return true;
}
return false;
}
// chmin (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmin(T &xmin, const U &x, Comp comp = {}) {
if (comp(x, xmin)) {
xmin = x;
return true;
}
return false;
}
// ローカル用
#define DEBUG_
#ifdef DEBUG_
#define DEB
#define dump(...) \
DUMPOUT << " " << string(#__VA_ARGS__) << ": " \
<< "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl \
<< " ", \
dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
struct AtCoderInitialize {
static constexpr int IOS_PREC = 15;
static constexpr bool AUTOFLUSH = false;
AtCoderInitialize() {
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cout << fixed << setprecision(IOS_PREC);
if (AUTOFLUSH) cout << unitbuf;
}
} ATCODER_INITIALIZE;
void Yn(bool p) { cout << (p ? "Yes" : "No") << endl; }
void YN(bool p) { cout << (p ? "YES" : "NO") << endl; }
/* #endregion */
// Problem
void solve() {
string s;
ll n;
cin >> s >> n;
vc<char> a(n), b(n);
REP(i, 0, n) cin >> a[i] >> b[i];
// dump(a, b);
vc<ll> conv(26);
vc<set<ll>> inv(26);
REP(i, 0, 26) {
conv[i] = i;
inv[i].insert(i);
}
// dump(conv, inv);
REP(i, 0, n) {
// dump(a[i], b[i]);
ll from = a[i] - 'A';
ll to = b[i] - 'A';
// いま from になっているもの(変換後に from になるやつ)が操作対象
set<ll> targets = inv[from];
inv[from] = set<ll>(); // clear
for (ll s : targets) {
conv[s] = to;
}
inv[to].merge(targets);
}
// dump(conv);
ll sz = SIZE(s);
REP(i, 0, sz) cout << (char)('A' + conv[s[i] - 'A']);
cout << endl;
}
// entry point
int main() {
solve();
return 0;
}

ステータス

項目 データ
問題 1337 - Cryptanalysis
ユーザー名 abb
投稿日時 2020-09-06 00:54:09
言語 C++17
状態 Accepted
得点 100
ソースコード長 6799 Byte
最大実行時間 65 ms
最大メモリ使用量 9244 KB

セット

セット 得点 Cases
1 ALL 100 / 100 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 61 ms 988 KB
1
in02.txt AC 31 ms 1380 KB
1
in03.txt AC 21 ms 1416 KB
1
in04.txt AC 28 ms 1764 KB
1
in05.txt AC 25 ms 2196 KB
1
in06.txt AC 28 ms 2656 KB
1
in07.txt AC 24 ms 2720 KB
1
in08.txt AC 51 ms 3108 KB
1
in09.txt AC 65 ms 3656 KB
1
in10.txt AC 23 ms 3472 KB
1
in11.txt AC 29 ms 3848 KB
1
in12.txt AC 27 ms 4044 KB
1
in13.txt AC 28 ms 4396 KB
1
in14.txt AC 24 ms 4656 KB
1
in15.txt AC 26 ms 5028 KB
1
in16.txt AC 26 ms 5548 KB
1
in17.txt AC 19 ms 5508 KB
1
in18.txt AC 26 ms 5728 KB
1
in19.txt AC 21 ms 5704 KB
1
in20.txt AC 19 ms 6244 KB
1
in21.txt AC 30 ms 6500 KB
1
in22.txt AC 31 ms 6748 KB
1
in23.txt AC 25 ms 7012 KB
1
in24.txt AC 31 ms 7268 KB
1
in25.txt AC 38 ms 7416 KB
1
in26.txt AC 26 ms 7768 KB
1
in27.txt AC 25 ms 8052 KB
1
in28.txt AC 22 ms 7800 KB
1
in29.txt AC 29 ms 8488 KB
1
in30.txt AC 49 ms 9244 KB
1
sample01.txt AC 28 ms 9020 KB
1
sample02.txt AC 24 ms 8976 KB
1
sample03.txt AC 38 ms 8928 KB
1