| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 274842 |
2020-08-19T16:42:09 Z |
sean9892 |
구간 성분 (KOI15_interval) |
C++14 |
|
1000 ms |
63864 KB |
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll=unsigned long long;
using pii=pair<ll,ll>;
ll ga[1510];
ll ha[1510];
ll gb[1510];
ll hb[1510];
set<pii> s;
ll p7[30];
ll p5[30];
const ll mod=9223372036854775783ll;
int res=0;
int main(void){
ios::sync_with_stdio(0);cin.tie(0);
{
ll a=1,b=1;
for(int i=0;i<26;i++){
p7[i]=a;
p5[i]=b;
a*=7;
b*=5;
a%=mod;
}
}
string a,b;
cin>>a>>b;
if(a.size()>b.size())swap(a,b);
ga[0]=gb[0]=ha[0]=hb[0]=0;
ga[1]=p7[('z'-a[0])];
ha[1]=p5[(a[0]-'a')^7];
for(int i=1;i<a.size();i++){
ga[i+1]=ga[i]+p7[('z'-a[i])];
if(ga[i+1]>=mod)ga[i+1]%=mod;
ha[i+1]=ha[i]+p5[(a[i]-'a')^7];
}
gb[1]=p7[('z'-b[0])];
hb[1]=p5[(b[0]-'a')^7];
for(int i=1;i<b.size();i++){
gb[i+1]=gb[i]+p7[('z'-b[i])];
if(gb[i+1]>=mod)gb[i+1]%=mod;
hb[i+1]=hb[i]+p5[(b[i]-'a')^7];
}
if(10ll*a.size()*a.size()*b.size()<=2e9){
for(int i=1;i<a.size();i++){
for(int j=0;j+res<i;j++){
for(int k=i-j;k<b.size();k++){
if(ha[i]-ha[j]==hb[k]-hb[k-i+j]){
res=max(res,i-j);
break;
}
}
}
}
cout<<res;
return 0;
}
for(int i=(int)a.size()-1;i>0;i--){
for(int j=0;j<i;j++){
ll x=ga[i]-ga[j];
ll y=ha[i]-ha[j];
s.insert(pii(x,y));
}
}
for(int i=(int)a.size()-1;i>0;i--){
for(int j=0;j+res<i;j++){
ll x=gb[i]-gb[j];
ll y=hb[i]-hb[j];
if(s.find(pii(x,y))!=s.end()){
res=max(res,i-j);
break;
}
}
}
cout<<res;
}
Compilation message
interval.cpp: In function 'int main()':
interval.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i=1;i<a.size();i++){
| ~^~~~~~~~~
interval.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=1;i<b.size();i++){
| ~^~~~~~~~~
interval.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=1;i<a.size();i++){
| ~^~~~~~~~~
interval.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int k=i-j;k<b.size();k++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
433 ms |
29408 KB |
Output is correct |
| 2 |
Correct |
303 ms |
30200 KB |
Output is correct |
| 3 |
Correct |
350 ms |
29944 KB |
Output is correct |
| 4 |
Correct |
451 ms |
29304 KB |
Output is correct |
| 5 |
Correct |
304 ms |
30200 KB |
Output is correct |
| 6 |
Correct |
395 ms |
29560 KB |
Output is correct |
| 7 |
Correct |
305 ms |
30212 KB |
Output is correct |
| 8 |
Correct |
301 ms |
30200 KB |
Output is correct |
| 9 |
Correct |
288 ms |
30328 KB |
Output is correct |
| 10 |
Correct |
295 ms |
30200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
360 ms |
16600 KB |
Output is correct |
| 2 |
Execution timed out |
1090 ms |
63864 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
