結果
問題 | No.2030 Googol Strings |
ユーザー |
|
提出日時 | 2022-08-05 22:25:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 58 ms / 2,000 ms |
コード長 | 1,767 bytes |
コンパイル時間 | 3,975 ms |
コンパイル使用メモリ | 230,824 KB |
実行使用メモリ | 20,004 KB |
最終ジャッジ日時 | 2024-09-15 19:34:10 |
合計ジャッジ時間 | 5,550 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 16 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using vi = vector<int>; using vvi = vector<vector<int>>; using pii = pair<int, int>; #define rep(i, n) for (int i = 0; i < (int)(n); ++i) #define repr(i, n) for (int i = (int)(n - 1); i >= 0; --i) struct MP { const string word; MP(const string &W) : word(W), table(W.size() + 1) { table[0] = -1; for (int i = 0, j = -1; i < W.size(); i++) { while (j >= 0 && W[i] != W[j]) j = table[j]; ++j; table[i + 1] = j; } return; } vi searchIn(const string &S) { int n = S.size(); vi ret(n); int m = 0, k = 0; while (m + k < S.size()) { if (S[m + k] == word[k]) { k++; if (k == word.size()) { ret[m] = k; m = m + k - table[k]; k = table[k]; } } else { ret[m] = k; m = m + k - table[k]; if (k > 0) k = table[k]; } } return ret; } private: vi table; }; int solve() { string x, y; cin >> x >> y; int r = 0; if (x.size() > y.size()) { swap(x, y); r = 1; } MP sv(x); vi res = sv.searchIn(y + y); int nx = x.size(), ny = y.size(); int c = 0; while (1) { if (res[c] < nx) { int k = res[c]; if (x[k] > y[(c + k) % ny]) r ^= 1; return r; } c = (c + nx) % ny; if (c == 0) break; } return r; } int main() { int T; cin >> T; rep(i, T) cout << (solve() ? 'X' : 'Y') << '\n'; return 0; }