#807016 (C++17) No.2102 [Cherry Alpha *] Conditional Reflection

提出ソース

結果

問題	No.2102 [Cherry Alpha *] Conditional Reflection
ユーザー	沙耶花
提出日時	2022-10-14 22:00:14
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	1,297 ms / 3,000 ms
コード長	2,412 bytes
コンパイル時間	5,535 ms
コンパイル使用メモリ	267,372 KB
実行使用メモリ	87,576 KB
最終ジャッジ日時	2023-09-08 21:20:27
合計ジャッジ時間	64,506 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	555 ms 26,044 KB
testcase_03	AC	722 ms 38,244 KB
testcase_04	AC	566 ms 24,792 KB
testcase_05	AC	373 ms 12,472 KB
testcase_06	AC	604 ms 26,312 KB
testcase_07	AC	921 ms 57,612 KB
testcase_08	AC	184 ms 4,500 KB
testcase_09	AC	793 ms 44,872 KB
testcase_10	AC	250 ms 9,464 KB
testcase_11	AC	219 ms 17,652 KB
testcase_12	AC	458 ms 24,924 KB
testcase_13	AC	894 ms 50,444 KB
testcase_14	AC	461 ms 18,676 KB
testcase_15	AC	695 ms 27,580 KB
testcase_16	AC	1,025 ms 48,300 KB
testcase_17	AC	525 ms 38,652 KB
testcase_18	AC	893 ms 56,700 KB
testcase_19	AC	311 ms 15,420 KB
testcase_20	AC	976 ms 53,944 KB
testcase_21	AC	313 ms 5,008 KB
testcase_22	AC	1,146 ms 56,232 KB
testcase_23	AC	1,145 ms 56,168 KB
testcase_24	AC	1,174 ms 56,216 KB
testcase_25	AC	1,126 ms 56,172 KB
testcase_26	AC	1,151 ms 56,256 KB
testcase_27	AC	1,146 ms 56,400 KB
testcase_28	AC	1,189 ms 56,132 KB
testcase_29	AC	1,181 ms 56,188 KB
testcase_30	AC	1,226 ms 56,156 KB
testcase_31	AC	1,266 ms 56,424 KB
testcase_32	AC	1,188 ms 56,204 KB
testcase_33	AC	1,189 ms 56,184 KB
testcase_34	AC	1,138 ms 56,280 KB
testcase_35	AC	1,173 ms 56,160 KB
testcase_36	AC	1,198 ms 56,372 KB
testcase_37	AC	1,168 ms 56,196 KB
testcase_38	AC	1,170 ms 56,356 KB
testcase_39	AC	1,154 ms 56,264 KB
testcase_40	AC	1,285 ms 56,120 KB
testcase_41	AC	1,218 ms 56,264 KB
testcase_42	AC	678 ms 21,632 KB
testcase_43	AC	671 ms 21,692 KB
testcase_44	AC	687 ms 21,648 KB
testcase_45	AC	697 ms 21,656 KB
testcase_46	AC	693 ms 21,948 KB
testcase_47	AC	1,176 ms 65,912 KB
testcase_48	AC	1,207 ms 65,852 KB
testcase_49	AC	1,220 ms 65,840 KB
testcase_50	AC	1,242 ms 65,872 KB
testcase_51	AC	1,237 ms 66,036 KB
testcase_52	AC	923 ms 87,496 KB
testcase_53	AC	927 ms 87,576 KB
testcase_54	AC	908 ms 87,532 KB
testcase_55	AC	1,044 ms 63,488 KB
testcase_56	AC	1,013 ms 63,568 KB
testcase_57	AC	983 ms 63,556 KB
testcase_58	AC	67 ms 16,384 KB
testcase_59	AC	1,297 ms 61,652 KB
testcase_60	AC	177 ms 4,384 KB
testcase_61	AC	1,033 ms 63,472 KB
testcase_62	AC	15 ms 4,376 KB
testcase_63	AC	216 ms 4,376 KB
testcase_64	AC	202 ms 4,376 KB
testcase_65	AC	242 ms 4,380 KB
testcase_66	AC	1,048 ms 63,044 KB
testcase_67	AC	350 ms 4,380 KB
testcase_68	AC	78 ms 4,380 KB
testcase_69	AC	344 ms 4,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 2000000000000000001
struct rolling_hash{

	long long t_hash;
	static vector<long long> power;
	static const long long MOD = (1LL<<61)-1;
	static const long long b = 123456;
	int sz;
	
	rolling_hash(){		
		sz = 0;
		t_hash = 0;
	}
	
	rolling_hash(char c){
		sz = 1;
		t_hash = b*c;
	}

	long long mul(__int128 x,__int128 y){
		__int128 t = x*y;
		t = (t>>61) + (t&MOD);
		
		if(t>=MOD)t -= MOD;
		return t;
	}
	
	long long get_pow(int sz){
		if(power.size()>sz)return power[sz];
		
		while(power.size()<=sz){
			if(power.size()==0)power.push_back(1);
			else power.push_back(mul(power.back(),b));
		}
		return power.back();
		
	}
	
	rolling_hash &operator+=(const rolling_hash &another){
		
		(*this).t_hash = mul((*this).t_hash,get_pow(another.sz));
		(*this).t_hash += another.t_hash;
		if((*this).t_hash>=MOD)(*this).t_hash -= MOD;
			
		(*this).sz += another.sz;
		
		return (*this);
	}
	
	rolling_hash operator+(const rolling_hash &another)const{
		return (rolling_hash(*this)+=another);
	}
	
	rolling_hash &operator-=(const rolling_hash &another){

		(*this).t_hash += MOD - mul(another.t_hash,get_pow((*this).sz-another.sz));
		if((*this).t_hash>=MOD)(*this).t_hash -= MOD;
			
		(*this).sz -= another.sz;

		return (*this);
	}
	
	rolling_hash operator-(const rolling_hash &another)const{
		return (rolling_hash(*this)-=another);
	}
	
	bool operator<(const rolling_hash &another)const{
		if((*this).t_hash!=another.t_hash)return (*this).t_hash<another.t_hash;
		return (*this).sz<another.sz;
	}
	
	bool operator==(const rolling_hash &another)const{
		return ((*this).t_hash==another.t_hash && (*this).sz==another.sz);
	}

	
};

vector<long long> rolling_hash::power;



int main(){
	
	int n;
	cin>>n;
	
	set<rolling_hash> S;
	
	rep(i,n){
		string s;
		cin>>s;
		int m = s.size();
		vector<rolling_hash> r(m+1);
		rep(j,m){
			r[j+1] = r[j] + rolling_hash(s[j]);
		}
		if(S.count(r[m])){
			cout<<"Yes"<<endl;
		}
		else{
			cout<<"No"<<endl;
		}
		S.insert(r[m]);
		rep(j,m-1){
			rolling_hash t;
			t = r[j];
			t = t + rolling_hash(s[j+1]);
			t = t + rolling_hash(s[j]);
			
			t = t + (r.back() - r[j+2]);
			//cout<<t.sz<<endl;
			S.insert(t);
		}
		
	}
		
	
	return 0;
}

yukicoder

結果

テストケース

ソースコード