結果
問題 | No.2102 [Cherry Alpha *] Conditional Reflection |
ユーザー |
![]() |
提出日時 | 2022-10-15 01:00:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,118 bytes |
コンパイル時間 | 2,336 ms |
コンパイル使用メモリ | 206,508 KB |
最終ジャッジ日時 | 2025-02-08 05:43:36 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 66 RE * 4 |
ソースコード
#define rep(i,n) for(int i=0;i<(int)(n);i++)#define ALL(v) v.begin(),v.end()typedef long long ll;#include<bits/stdc++.h>using namespace std;ll MOD1=465290608031;ll MOD2=653371827107;int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);random_device rd;mt19937_64 rnd(rd());uniform_int_distribution<ll> dist_n1(1000001,999999999),dist_n2(1000001,999999999);int n;cin>>n;vector<string> S(n);rep(i,n) cin>>S[i];vector<ll> A(n),B(n);rep(i,n){ll a=dist_n1(rnd),b=dist_n2(rnd);A[i]=a,B[i]=b;}set<pair<ll,ll>> s;rep(i,n){ll sum1=0,sum2=0;int k=S[i].size();rep(j,k){sum1=(sum1+A[j]*S[i][j]%MOD1)%MOD1;sum2=(sum2+B[j]*S[i][j]%MOD2)%MOD2;}if(s.count({sum1,sum2})) cout<<"Yes"<<'\n';else cout<<"No"<<'\n';s.insert({sum1,sum2});rep(j,k-1){ll a=(sum1-A[j]*S[i][j]%MOD1-A[j+1]*S[i][j+1]%MOD1+A[j]*S[i][j+1]+A[j+1]*S[i][j]+2*MOD1)%MOD1;ll b=(sum2-B[j]*S[i][j]%MOD2-B[j+1]*S[i][j+1]%MOD2+B[j]*S[i][j+1]+B[j+1]*S[i][j]+2*MOD2)%MOD2;s.insert({a,b});}}return 0;}