結果
問題 | No.2102 [Cherry Alpha *] Conditional Reflection |
ユーザー |
![]() |
提出日時 | 2022-10-15 00:51:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,114 bytes |
コンパイル時間 | 2,368 ms |
コンパイル使用メモリ | 206,428 KB |
最終ジャッジ日時 | 2025-02-08 05:39:00 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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=698468298355739;ll MOD2=301781318234953;int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);random_device rd;mt19937_64 rnd(rd());uniform_int_distribution<ll> dist_n1(100000001,999999999999),dist_n2(100000001,999999999999);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"<<endl;else cout<<"No"<<endl;s.insert({sum1,sum2});rep(j,k-1){ll a=(sum1-A[j]*S[i][j]-A[j+1]*S[i][j+1]+A[j]*S[i][j+1]+A[j+1]*S[i][j]+2*MOD1)%MOD1;ll b=(sum2-B[j]*S[i][j]-B[j+1]*S[i][j+1]+B[j]*S[i][j+1]+B[j+1]*S[i][j]+2*MOD2)%MOD2;s.insert({a,b});}}return 0;}