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
|