Task: | Counting Words |
Sender: | Hannes Ihalainen |
Submission time: | 2017-11-21 21:11:06 +0200 |
Language: | C++ |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | WRONG ANSWER | 0.25 s | details |
#2 | WRONG ANSWER | 0.22 s | details |
#3 | WRONG ANSWER | 0.38 s | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:57:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i=0; i<s.size(); ++i) k.push_back(s[i]-'?'); ^
Code
#include <bits/stdc++.h> using namespace std; string s; int w; vector<int> suffixArray(vector<int> s, int S){ int n=s.size(); int N=n+S; vector<int> sa(n), ra(n); for (int i=0; i<n; ++i) { sa[i]=i; ra[i]=s[i];} for (int k=0; k<n; k?k*=2:k++){ vector<int> nsa(sa), nra(n), cnt(N); for (int i=0; i<n; ++i) nsa[i]=(nsa[i]-k+n)%n; for (int i=0; i<n; ++i) cnt[ra[i]]++; for (int i=1; i<N; ++i) cnt[i]+=cnt[i-1]; for (int i=n-1; i>=0; --i) sa[--cnt[ra[nsa[i]]]]=nsa[i]; int r=0; for (int i=1; i<n; ++i){ if (ra[sa[i]]!=ra[sa[i-1]]) ++r; else if (ra[(sa[i]+k)%n]!=ra[(sa[i-1]+k)%n]) ++r; nra[sa[i]]=r; } ra=nra; } return sa; } int pos[101010]; int pose[101010]; int id[202020]; int ide[202020]; int ans[202020]; int t[101010]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> s; int n; n=s.size(); cin >> w; s.push_back('@'); for (int i=1; i<=w; ++i){ string t; cin >> t; pos[i]=s.size(); id[s.size()]=i; s+=t; s.push_back('?'); pose[i]=s.size(); ide[s.size()]=i; s+=t; s.push_back('['); } vector<int> k; for (int i=0; i<s.size(); ++i) k.push_back(s[i]-'?'); vector<int> sa=suffixArray(k, 30); // for (auto c : s) cout << c << " "; cout << endl; // return 0; int s=0; for (auto k : sa) { if (id[k]){ t[id[k]]=s; }else if (ide[k]){ ans[ide[k]]=s-t[ide[k]]; }else{ if (k<n) ++s; } } for (int i=1; i<=w; ++i) cout << ans[i] << "\n"; }
Test details
Test 1
Verdict: WRONG ANSWER
input |
---|
ZIAHIAMHKVFZTCVAZPFWSXHXUDFQXP... |
correct output |
---|
999 999 999 1000 999 ... |
user output |
---|
992 995 995 993 994 ... |
Test 2
Verdict: WRONG ANSWER
input |
---|
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |
correct output |
---|
100000 99999 99998 99997 99996 ... |
user output |
---|
99872 99871 99870 99869 99868 ... |
Test 3
Verdict: WRONG ANSWER
input |
---|
BBABABBABBABAAABABABAABABABAAB... |
correct output |
---|
100 104 80 100 98 ... |
user output |
---|
93 89299 46904 94 63498 ... |