結果
問題 | No.2102 [Cherry Alpha *] Conditional Reflection |
ユーザー |
![]() |
提出日時 | 2022-10-14 22:33:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,425 ms / 3,000 ms |
コード長 | 1,736 bytes |
コンパイル時間 | 2,004 ms |
コンパイル使用メモリ | 176,912 KB |
実行使用メモリ | 57,228 KB |
最終ジャッジ日時 | 2024-06-26 15:57:54 |
合計ジャッジ時間 | 71,531 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 70 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long BASE = 100000000; const unsigned long long M30 = ((unsigned long long) 1 << 30) - 1; const unsigned long long M31 = ((unsigned long long) 1 << 31) - 1; const unsigned long long MOD = ((unsigned long long) 1 << 61) - 1; unsigned long long modulo(unsigned long long x){ unsigned long long xu = x >> 61; unsigned long long xd = x & MOD; unsigned long long res = xu + xd; if (res >= MOD){ res -= MOD; } return res; } unsigned long long mul(unsigned long long a, unsigned long long b){ unsigned long long au = a >> 31; unsigned long long ad = a & M31; unsigned long long bu = b >> 31; unsigned long long bd = b & M31; unsigned long long mid = au * bd + ad * bu; unsigned long long midu = mid >> 30; unsigned long long midd = mid & M30; return modulo(au * bu * 2 + midu + (midd << 31) + ad * bd); } int main(){ int N; cin >> N; vector<string> S(N); for (int i = 0; i < N; i++){ cin >> S[i]; } set<unsigned long long> st; for (int i = 0; i < N; i++){ int L = S[i].size(); vector<long long> POW(L); POW[0] = 1; for (int j = 1; j < L; j++){ POW[j] = mul(POW[j - 1], BASE); } unsigned long long sum = 0; for (int j = 0; j < L; j++){ sum = modulo(sum + mul(S[i][j], POW[j])); } if (st.count(sum) == 1){ cout << "Yes" << endl; } else { cout << "No" << endl; } st.insert(sum); for (int j = 0; j < L - 1; j++){ unsigned long long sum2 = sum; sum2 += MOD - mul(S[i][j], POW[j]); sum2 += MOD - mul(S[i][j + 1], POW[j + 1]); sum2 += mul(S[i][j], POW[j + 1]); sum2 += mul(S[i][j + 1], POW[j]); st.insert(modulo(sum2)); } } }