Task: | Family chronicle |
Sender: | Pohjantahti |
Submission time: | 2018-10-13 15:10:21 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.01 s | details |
#2 | ACCEPTED | 0.03 s | details |
#3 | ACCEPTED | 0.02 s | details |
#4 | ACCEPTED | 0.01 s | details |
#5 | ACCEPTED | 0.02 s | details |
#6 | ACCEPTED | 0.01 s | details |
#7 | ACCEPTED | 0.02 s | details |
#8 | ACCEPTED | 0.01 s | details |
#9 | ACCEPTED | 0.02 s | details |
#10 | ACCEPTED | 0.02 s | details |
#11 | ACCEPTED | 0.02 s | details |
#12 | ACCEPTED | 0.02 s | details |
#13 | ACCEPTED | 0.03 s | details |
#14 | ACCEPTED | 0.02 s | details |
#15 | ACCEPTED | 0.05 s | details |
#16 | ACCEPTED | 0.05 s | details |
#17 | ACCEPTED | 0.36 s | details |
#18 | ACCEPTED | 0.08 s | details |
#19 | ACCEPTED | 0.34 s | details |
#20 | ACCEPTED | 0.29 s | details |
#21 | ACCEPTED | 0.06 s | details |
#22 | ACCEPTED | 0.21 s | details |
#23 | ACCEPTED | 0.16 s | details |
#24 | ACCEPTED | 0.33 s | details |
#25 | ACCEPTED | 0.21 s | details |
#26 | ACCEPTED | 0.05 s | details |
#27 | ACCEPTED | 0.33 s | details |
#28 | ACCEPTED | 0.43 s | details |
#29 | ACCEPTED | 0.07 s | details |
#30 | ACCEPTED | 0.05 s | details |
#31 | ACCEPTED | 0.43 s | details |
#32 | ACCEPTED | 0.05 s | details |
#33 | ACCEPTED | 0.16 s | details |
#34 | ACCEPTED | 0.09 s | details |
#35 | ACCEPTED | 0.38 s | details |
#36 | ACCEPTED | 0.06 s | details |
#37 | ACCEPTED | 0.05 s | details |
#38 | ACCEPTED | 0.28 s | details |
#39 | ACCEPTED | 0.27 s | details |
#40 | ACCEPTED | 0.07 s | details |
Compiler report
input/code.cpp: In function 'll shash(std::__cxx11::string)': input/code.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 1; i < cs.length(); ++i) { ~~^~~~~~~~~~~~~ input/code.cpp: In function 'll shash2(std::__cxx11::string)': input/code.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 1; i < cs.length(); ++i) { ~~^~~~~~~~~~~~~ input/code.cpp: In function 'int main()': input/code.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 1; i < s.length(); ++i) { ~~^~~~~~~~~~~~
Code
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("arch=skylake") #include <iostream> #include <string> #include <vector> #include <set> #include <unordered_set> #include <map> using namespace std; typedef long long ll; const ll A = 945829483; const ll B = 1000000007; const ll C = 772349821; const ll D = 1000000009; string s; int q; vector<string> pt; set<int> lens; unordered_set<ll> hashes; map<ll, vector<int>> hi; bool res[50005]; ll h[50005]; ll p[50005]; ll h2[50005]; ll p2[50005]; ll ghash(int a, int b) { if (a == 0) return h[b]; ll cres = (h[b]-h[a-1]*p[b-a+1])%B; if (cres < 0) cres += B; return cres; } ll ghash2(int a, int b) { if (a == 0) return h2[b]; ll cres = (h2[b]-h2[a-1]*p2[b-a+1])%D; if (cres < 0) cres += D; return cres; } ll shash(string cs) { ll ch = cs[0]; for (int i = 1; i < cs.length(); ++i) { ch = (ch*A+cs[i])%B; } return ch; } ll shash2(string cs) { ll ch = cs[0]; for (int i = 1; i < cs.length(); ++i) { ch = (ch*C+cs[i])%D; } return ch; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> s; cin >> q; for (int i = 0; i < q; ++i) { string cs; cin >> cs; pt.push_back(cs); lens.insert(cs.length()); } h[0] = s[0]; p[0] = 1; h2[0] = s[0]; p2[0] = 1; for (int i = 1; i < s.length(); ++i) { h[i] = (h[i-1]*A+s[i])%B; p[i] = (p[i-1]*A)%B; h2[i] = (h2[i-1]*C+s[i])%D; p2[i] = (p2[i-1]*C)%D; } for (int i = 0; i < q; ++i) { ll chash = shash(pt[i]); chash *= shash2(pt[i]); hashes.insert(chash); hi[chash].push_back(i); } for (int cl : lens) { for (int i = 0; i < ((int)s.length())-(cl-1); ++i) { ll chash = ghash(i, i+(cl-1)); chash *= ghash2(i, i+(cl-1)); if (hashes.find(chash) != hashes.end()) { for (int a : hi[chash]) { res[a] = true; } hashes.erase(chash); } } } for (int i = 0; i < q; ++i) { if (res[i]) cout << "YES\n"; else cout << "NO\n"; } return 0; }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
NOLLFDD 4 D F GD ... |
correct output |
---|
YES YES NO YES |
user output |
---|
YES YES NO YES |
Test 2
Verdict: ACCEPTED
input |
---|
NLHIJHFLL 4 LH IJX U ... |
correct output |
---|
YES NO NO NO |
user output |
---|
YES NO NO NO |
Test 3
Verdict: ACCEPTED
input |
---|
KMLZVXCDAAK 5 CDAA MAZ DA ... |
correct output |
---|
YES NO YES NO YES |
user output |
---|
YES NO YES NO YES |
Test 4
Verdict: ACCEPTED
input |
---|
YSKBJNAQNAXDCJ 6 C YJKB KC ... |
correct output |
---|
YES NO NO YES YES ... |
user output |
---|
YES NO NO YES YES ... |
Test 5
Verdict: ACCEPTED
input |
---|
SUNSZYCIPNOKBKYOSH 6 KEK ZQC E ... |
correct output |
---|
NO NO NO YES NO ... |
user output |
---|
NO NO NO YES NO ... |
Test 6
Verdict: ACCEPTED
input |
---|
PEEKYVCXKPRDFBIQBCMOOD 6 Z I WK ... |
correct output |
---|
NO YES NO YES NO ... |
user output |
---|
NO YES NO YES NO ... |
Test 7
Verdict: ACCEPTED
input |
---|
WFFFWXFWFFXXXFWXWWWFWWFFWFFFWF... |
correct output |
---|
YES YES NO YES |
user output |
---|
YES YES NO YES |
Test 8
Verdict: ACCEPTED
input |
---|
MMWTJEOANERJSZVWPTHGUPBVEIXFUH... |
correct output |
---|
YES YES YES NO YES ... |
user output |
---|
YES YES YES NO YES ... |
Test 9
Verdict: ACCEPTED
input |
---|
SXSXXXXXXXXXXXXXSXXXXXXXXXXXXX... |
correct output |
---|
YES YES YES YES YES |
user output |
---|
YES YES YES YES YES |
Test 10
Verdict: ACCEPTED
input |
---|
EWLWHMLGWWLBOZNDUOANXGJUDTFUVJ... |
correct output |
---|
YES NO YES YES YES ... |
user output |
---|
YES NO YES YES YES ... |
Test 11
Verdict: ACCEPTED
input |
---|
RRPPRRPPPPPRRPPPPPPPPPPRPRRRPP... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... |
Test 12
Verdict: ACCEPTED
input |
---|
ZWPOBWAZUUXXOHBHAPPLOOBAHZWPGO... |
correct output |
---|
NO YES NO NO YES ... |
user output |
---|
NO YES NO NO YES ... |
Test 13
Verdict: ACCEPTED
input |
---|
KQOANBJEFBYZKANIJUCUXAUEPKJFGO... |
correct output |
---|
YES NO YES YES NO ... |
user output |
---|
YES NO YES YES NO ... |
Test 14
Verdict: ACCEPTED
input |
---|
KLEFLAALELPKWAPEKKKAPLAEFEKATL... |
correct output |
---|
NO YES YES YES YES ... |
user output |
---|
NO YES YES YES YES ... |
Test 15
Verdict: ACCEPTED
input |
---|
ZKGGKUKKKGKGGKUGUUKKGUGGKUOKGG... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... |
Test 16
Verdict: ACCEPTED
input |
---|
RRRRRRRRRRRVRQRRQRRRRRRRRQRRRR... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... |
Test 17
Verdict: ACCEPTED
input |
---|
OYWWPKKSYYCEHRWIKSKSEDPDBABIOF... |
correct output |
---|
YES YES YES NO YES ... |
user output |
---|
YES YES YES NO YES ... |
Test 18
Verdict: ACCEPTED
input |
---|
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... |
Test 19
Verdict: ACCEPTED
input |
---|
GGGGGGWGWGGWWGWGWGWWGWWWGWGGGW... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... |
Test 20
Verdict: ACCEPTED
input |
---|
QVQQQVBVQBVQQVIVIVQVQQBQQQBQQV... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... |
Test 21
Verdict: ACCEPTED
input |
---|
STUZEDPGLJKQXBPYTQVKDXSVZAOYPO... |
correct output |
---|
YES NO NO NO NO ... |
user output |
---|
YES NO NO NO NO ... |
Test 22
Verdict: ACCEPTED
input |
---|
ZTJZMZMMJDJMMTMJNZDGJDJJMGTNZM... |
correct output |
---|
NO NO NO YES NO ... |
user output |
---|
NO NO NO YES NO ... |
Test 23
Verdict: ACCEPTED
input |
---|
JJTJJTTJTJTJTJTJTTTTTJTJJJTTTT... |
correct output |
---|
YES YES YES YES NO ... |
user output |
---|
YES YES YES YES NO ... |
Test 24
Verdict: ACCEPTED
input |
---|
QLQQLQQLQQQQQLQLQLLLQQQQLLLLLL... |
correct output |
---|
YES NO YES YES YES ... |
user output |
---|
YES NO YES YES YES ... |
Test 25
Verdict: ACCEPTED
input |
---|
EECBCBBECECBBBCEBEECBCCCECEBBC... |
correct output |
---|
YES YES NO NO YES ... |
user output |
---|
YES YES NO NO YES ... |
Test 26
Verdict: ACCEPTED
input |
---|
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... |
Test 27
Verdict: ACCEPTED
input |
---|
GYUIJZOSVBNNHBJFZXJCTAGYHEOEYI... |
correct output |
---|
YES YES YES YES NO ... |
user output |
---|
YES YES YES YES NO ... |
Test 28
Verdict: ACCEPTED
input |
---|
PKMQQIWPQNFJFTBCLAMSMAZHLIQOKK... |
correct output |
---|
YES NO YES YES NO ... |
user output |
---|
YES NO YES YES NO ... |
Test 29
Verdict: ACCEPTED
input |
---|
UCYZBQRZDPTDFDICDCVZPDCUPGYZZF... |
correct output |
---|
YES YES YES NO YES ... |
user output |
---|
YES YES YES NO YES ... |
Test 30
Verdict: ACCEPTED
input |
---|
PPPPPPPPPPPPPPPPPPPPPPPPPDPPDP... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... |
Test 31
Verdict: ACCEPTED
input |
---|
EEENNEEEENNNNEENENNNEENENEEENE... |
correct output |
---|
YES NO YES YES YES ... |
user output |
---|
YES NO YES YES YES ... |
Test 32
Verdict: ACCEPTED
input |
---|
FWVMCMYKALJMZEQPKUCRTUGDNUJOHB... |
correct output |
---|
NO YES NO YES YES ... |
user output |
---|
NO YES NO YES YES ... |
Test 33
Verdict: ACCEPTED
input |
---|
UUUUUUUUUUUUUUUUUUUUHUUUUUUUUU... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... |
Test 34
Verdict: ACCEPTED
input |
---|
IIIIOIIIFIIIIIIIOOIIIIOOIIIFII... |
correct output |
---|
NO NO YES NO YES ... |
user output |
---|
NO NO YES NO YES ... |
Test 35
Verdict: ACCEPTED
input |
---|
PPIPUIBPIIXUCICPIUCIOPXUXIIIUX... |
correct output |
---|
YES NO YES NO YES ... |
user output |
---|
YES NO YES NO YES ... |
Test 36
Verdict: ACCEPTED
input |
---|
AYYYYAYAAAAAJAAAWAAYAYAYIAWYYY... |
correct output |
---|
YES YES NO YES YES ... |
user output |
---|
YES YES NO YES YES ... |
Test 37
Verdict: ACCEPTED
input |
---|
AAAEAANNANEAEAEAPEAAAAAEAAAEAA... |
correct output |
---|
NO NO YES NO YES ... |
user output |
---|
NO NO YES NO YES ... |
Test 38
Verdict: ACCEPTED
input |
---|
PPPPLKPTKZPZPKGPPKZKPPPPPLPPSP... |
correct output |
---|
YES YES YES YES YES ... |
user output |
---|
YES YES YES YES YES ... |
Test 39
Verdict: ACCEPTED
input |
---|
AAOOOOAAOOAAOOAOOOOAAOAAAAAAAO... |
correct output |
---|
YES NO YES YES YES ... |
user output |
---|
YES NO YES YES YES ... |
Test 40
Verdict: ACCEPTED
input |
---|
QSCCSWNRLLTWPQCGJSZCLPJJVUXJJR... |
correct output |
---|
YES YES YES YES NO ... |
user output |
---|
YES YES YES YES NO ... |