Submission #276756

#	Time	Username	Problem	Language	Result	Execution time	Memory
276756		sean9892	구간 성분 (KOI15_interval)	C++14	100 / 100	438 ms	32376 KiB

interval

#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 (stderr)

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 / 7
• Subtask 2: 23 / 23
• Subtask 3: 31 / 31
• Subtask 4: 39 / 39