oj.uz

답안 #276756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
276756 2020-08-20T16:15:37 Z sean9892 구간 성분 (KOI15_interval) C++14
100 / 100
 438 ms 32376 KB 
#include<bits/stdc++.h>
using namespace std;
using ll=unsigned long long;
using pii=pair<ll,int>;

const int ma=(1<<17)-1;
const ll mb=1e9+7;

vector<int> pr;
vector<pii> h[ma];

int main(void){
	ios::sync_with_stdio(0);cin.tie(0);
	string a,b;
	cin>>a>>b;
	
	for(int i=2;i<10000;i++){
		int flag=1;
		for(int j=2;j*j<=i;j++){
			if(i%j==0){
				flag=0;
				break;
			}
		}
		if(flag){
			pr.push_back(i);
		}
	}
	
	//hash A
	{
		for(int i=0;i<a.size();i++){
			int x=1;
			ll y=1;
			for(int j=i;j<a.size();j++){
				int l=j-i+1;
				int k=a[j]-'a';
				x*=pr[k];
				y*=pr[k+30];
				x%=ma;y%=mb;
				h[x].push_back(pii(y,l));
			}
		}
	}
	int res=0;
	//hash B
	{
		for(int i=0;i<b.size();i++){
			int x=1;
			ll y=1;
			for(int j=i;j<b.size();j++){
				int l=j-i+1;
				int k=b[j]-'a';
				x*=pr[k];
				y*=pr[k+30];
				x%=ma;y%=mb;
				int flag=0;
				for(int w=0;w<h[x].size();w++){
					if(h[x][w]==pii(y,l)){
						flag=1;
						break;
					}
				}
				if(flag){
					res=max(res,l);
				}
			}
		}
	}
	cout<<res;
}

Compilation message

interval.cpp: In function 'int main()':
interval.cpp:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i=0;i<a.size();i++){
      |               ~^~~~~~~~~
interval.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for(int j=i;j<a.size();j++){
      |                ~^~~~~~~~~
interval.cpp:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int i=0;i<b.size();i++){
      |               ~^~~~~~~~~
interval.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    for(int j=i;j<b.size();j++){
      |                ~^~~~~~~~~
interval.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long unsigned int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int w=0;w<h[x].size();w++){
      |                 ~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3456 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 4 ms 3584 KB Output is correct
4 Correct 4 ms 3584 KB Output is correct
5 Correct 4 ms 3584 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 5612 KB Output is correct
2 Correct 29 ms 6652 KB Output is correct
3 Correct 19 ms 6656 KB Output is correct
4 Correct 11 ms 5760 KB Output is correct
5 Correct 29 ms 6784 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 16376 KB Output is correct
2 Correct 178 ms 16376 KB Output is correct
3 Correct 176 ms 16376 KB Output is correct
4 Correct 168 ms 16376 KB Output is correct
5 Correct 149 ms 16376 KB Output is correct
6 Correct 149 ms 16408 KB Output is correct
7 Correct 146 ms 16376 KB Output is correct
8 Correct 151 ms 16376 KB Output is correct
9 Correct 146 ms 16376 KB Output is correct
10 Correct 151 ms 16504 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 20600 KB Output is correct
2 Correct 355 ms 32280 KB Output is correct
3 Correct 357 ms 31992 KB Output is correct
4 Correct 269 ms 29688 KB Output is correct
5 Correct 438 ms 32376 KB Output is correct