oj.uz

Submission #274817

# Submission time Handle Problem Language Result Execution time Memory
274817 2020-08-19T16:13:40 Z sean9892 구간 성분 (KOI15_interval) C++14
31 / 100
 1000 ms 62612 KB 
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using pii=pair<ll,ll>;
ll ga[1510];
ll ha[1510];
ll gb[1510];
ll hb[1510];
set<pii> s;

ll ipow(ll x,int n){
	if(n==0)return 1;
	if(n==1)return x;
	if(n&1)return ipow(x*x,n/2)*x;
	return ipow(x*x,n/2);
}

int res=0;

int main(void){
	ios::sync_with_stdio(0);cin.tie(0);
	string a,b;
	cin>>a>>b;
	
	ga[1]=ipow(3,a[0]-'a'+26*(a[0]-'a')-13);
	ha[1]=ipow(5,a[0]-'a');
	for(int i=1;i<a.size();i++){
		ga[i+1]=ga[i]+ipow(3,a[i]-'a'+26*(a[i]-'a')-13);
		ha[i+1]=ha[i]+ipow(5,a[i]-'a');
	}
	gb[1]=ipow(3,b[0]-'a'+26*(b[0]-'a')-13);
	hb[1]=ipow(5,b[0]-'a');
	for(int i=1;i<b.size();i++){
		gb[i+1]=gb[i]+ipow(3,b[i]-'a'+26*(b[i]-'a')-13);
		hb[i+1]=hb[i]+ipow(5,b[i]-'a');
	}
	
	for(int i=1;i<a.size();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=1;i<b.size();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;
			}
		}
	}
	printf("%d",res);
}

Compilation message

interval.cpp: In function 'int main()':
interval.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i=1;i<a.size();i++){
      |              ~^~~~~~~~~
interval.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=1;i<b.size();i++){
      |              ~^~~~~~~~~
interval.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=1;i<a.size();i++){
      |              ~^~~~~~~~~
interval.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=1;i<b.size();i++){
      |              ~^~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 5120 KB Output is correct
2 Correct 62 ms 6392 KB Output is correct
3 Correct 14 ms 640 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 29048 KB Output is correct
2 Correct 745 ms 30192 KB Output is correct
3 Correct 897 ms 29816 KB Output is correct
4 Correct 779 ms 29176 KB Output is correct
5 Correct 862 ms 30200 KB Output is correct
6 Correct 760 ms 29348 KB Output is correct
7 Correct 814 ms 30232 KB Output is correct
8 Correct 829 ms 30184 KB Output is correct
9 Correct 862 ms 30040 KB Output is correct
10 Correct 863 ms 30024 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 11768 KB Output is correct
2 Execution timed out 1092 ms 62612 KB Time limit exceeded
3 Halted 0 ms 0 KB -