제출 #274821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
274821		sean9892	구간 성분 (KOI15_interval)	C++14	0 / 100	282 ms	29048 KiB

interval

#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#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 p3[30];
ll p5[30];

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++){
			p3[i]=a;
			p5[i]=b;
			a*=3;
			b*=5;
		}
	}
	string a,b;
	cin>>a>>b;
	
	ga[1]=p3[a[0]-'a'+26*(a[0]-'a')-13];
	ha[1]=p5[a[0]-'a'];
	for(int i=1;i<a.size();i++){
		ga[i+1]=ga[i]+p3[a[i]-'a'+26*(a[i]-'a')-13];
		ha[i+1]=ha[i]+p5[a[i]-'a'];
	}
	gb[1]=p3[b[0]-'a'+26*(b[0]-'a')-13];
	hb[1]=p5[b[0]-'a'];
	for(int i=1;i<b.size();i++){
		gb[i+1]=gb[i]+p3[b[i]-'a'+26*(b[i]-'a')-13];
		hb[i+1]=hb[i]+p5[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);
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 31
• Subtask 4: 0 / 39