oj.uz

답안 #274842

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
274842 2020-08-19T16:42:09 Z sean9892 구간 성분 (KOI15_interval) C++14
31 / 100
 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++){
      |                   ~^~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 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

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 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 -