F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 3916 >> 程序CE
zP1nG @ 2018-06-11 15:42:03
[ Quote ] [ Edit ] [ Delete ] 1#
代码如下:
#include<bits/stdc++.h>
#define N 2000001
#define base1 41
#define base2 131
using namespace std;
int n,l,po1_[N]={1},po2_[N]={1},h1_[N],h2_[N],num,ans1,ans2,loc;
char s[N+5];
int main(){
for(int i=1;i<=N;++i) po1_[i]=po1_[i-1]*base1;
for(int i=1;i<=N;++i) po2_[i]=po2_[i-1]*base2;
scanf("%d%s",&n,s+1),l=n>>1;
if(!(n&1)){
puts("NOT POSSIBLE");
return 0;
}
for(int i=1;i<=n;++i) h1_[i]=h1_[i-1]*base1+s[i]-'A'+1;
for(int i=1;i<=n;++i) h2_[i]=h2_[i-1]*base2+s[i]-'A'+1;
for(int p1=h1_[n]-h1_[l+1]*po1_[l],p2=h2_[n]-h2_[l+1]*po2_[l],len=l,v1,v2,i=1;i<=l;++i,len=l+1-i){
if((v1=h1_[l+1]-h1_[i]*po1_[len]+h1_[i-1]*po1_[len])==p1 && (v2=h2_[l+1]-h2_[i]*po2_[len]+h2_[i-1]*po2_[len])==p2){
if(!num) ++num,ans1=v1,ans2=v2,loc=i;
else if(ans1^v1 || ans2^v2){
++num;
puts("NOT UNIQUE");
return 0;
}
}
}
if(h1_[n]-h1_[l+1]*po1_[l]==h1_[l] && h2_[n]-h2_[l+1]*po2_[l]==h2_[l]){
if(!num) ++num,ans1=h1_[l],ans2=h2_[l],loc=l+1;
else if(ans1^h1_[l] || ans2^h2_[l]){
++num;
puts("NOT UNIQUE");
return 0;
}
}
for(int p1=h1_[l],p2=h2_[l],len1=1,len2=n-l-2,v1,v2,i=l+2;i<=n;++i,len1=i-l-1,len2=n-i){
if((v1=h1_[n]-h1_[n-len2]*po1_[len2]+(h1_[i-1]-h1_[l]*po1_[len1])*po1_[len2])==p1 && (v2=h2_[n]-h2_[n-len2]*po2_[len2]+(h2_[i-1]-h2_[l]*po2_[len1])*po2_[len2])==p2){
if(!num) ++num,ans1=v1,ans2=v2,loc=i;
else if(ans1^v1 || ans2^v2){
++num;
puts("NOT UNIQUE");
return 0;
}
}
}
if(!num) puts("NOT POSSIBLE");
else{
if(loc<=l)
for(int i=l+2;i<=n;++i) printf("%c",s[i]);
else
for(int i=1;i<=l;++i) printf("%c",s[i]);
puts("");
}
return 0;
}
info如下:
Main.cc: In function 'int main()':
Main.cc:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result
g++: Internal error: File size limit exceeded (program as)
Please submit a full bug report.
See <file:///usr/share/doc/gcc-4.4/README.Bugs> for instructions.
怎么办???
TLECODE @ 2018-08-21 08:45:07
[ Quote ] [ Edit ] [ Delete ] 2#
只用一个hash应该就可以了
TLECODE @ 2018-08-21 08:46:59
[ Quote ] [ Edit ] [ Delete ] 3#
我用两个hash也是一样的CE
[Top] [Previous Page] [Next Page]

HOME Back