oj.uz

답안 #602724

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
602724 2022-07-23T10:45:53 Z WongChun1234 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
25 / 85
 1500 ms 184024 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=3499999991;
int n,m,ans,l,r;
ll hsh[2][3050],prec[3050];
string a,b;
map<string,int> hv;
void computehash(int id,string str){
	for (int i=1;i<str.length();i++){
		hsh[id][i]=hsh[id][i-1]*27+str[i]-'a'+1;
		hsh[id][i]%=MOD;
	}
}
string gethash(int id,int l,int r){
	string ret="";
	if (id) for (int i=l+1;i<=r;i++) ret+=b[i];
	else for (int i=l+1;i<=r;i++) ret+=a[i];
	return ret;
}
int main(){
	cin>>a>>b;
	a=' '+a;
	b=' '+b;
	computehash(0,a);
	computehash(1,b);
	prec[0]=1;
	for (int i=1;i<=3000;i++) prec[i]=prec[i-1]*27%MOD;
	for (int i=1;i<a.length();i++){
		for (int j=i;j<a.length();j++){
			for (int k=0;k<i;k++){
				//cout<<i<<"-"<<j<<"--"<<k<<"::"<<(gethash(0,i-1,j)*prec[i-k-1]+gethash(0,k,i-1))%MOD<<"\n";
				hv[gethash(0,i-1,j)+gethash(0,k,i-1)]=k+1;
			}
		}
	}
	for (int i=1;i<b.length();i++){
		for (int j=i;j<b.length();j++){
			for (int k=0;k<i;k++){
				//cout<<i<<"-"<<j<<"--"<<k<<"::"<<(gethash(1,i-1,j)*prec[i-k-1]+gethash(1,k,i-1))%MOD<<"\n";
				if (!hv[gethash(1,i-1,j)+gethash(1,k,i-1)]) continue;
				if (j-k<ans) continue;
				ans=j-k;
				l=hv[gethash(1,i-1,j)+gethash(1,k,i-1)]-1;
				r=k;
			}
		}
	}
	reverse(b.begin()+1,b.end());
	computehash(1,b);
	for (int i=1;i<b.length();i++){
		for (int j=i;j<b.length();j++){
			for (int k=0;k<i;k++){
				//cout<<i<<"-"<<j<<"--"<<k<<"::"<<(gethash(1,i-1,j)*prec[i-k-1]+gethash(1,k,i-1))%MOD<<"\n";
				if (!hv[gethash(1,i-1,j)+gethash(1,k,i-1)]) continue;
				if (j-k<ans) continue;
				ans=j-k;
				l=hv[gethash(1,i-1,j)+gethash(1,k,i-1)]-1;
				r=b.length()-1-j;
			}
		}
	}
	cout<<ans<<"\n"<<l<<" "<<r<<"\n";
}

Compilation message

necklace.cpp: In function 'void computehash(int, std::string)':
necklace.cpp:10:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for (int i=1;i<str.length();i++){
      |               ~^~~~~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (int i=1;i<a.length();i++){
      |               ~^~~~~~~~~~~
necklace.cpp:30:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for (int j=i;j<a.length();j++){
      |                ~^~~~~~~~~~~
necklace.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i=1;i<b.length();i++){
      |               ~^~~~~~~~~~~
necklace.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (int j=i;j<b.length();j++){
      |                ~^~~~~~~~~~~
necklace.cpp:51:16: 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 i=1;i<b.length();i++){
      |               ~^~~~~~~~~~~
necklace.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int j=i;j<b.length();j++){
      |                ~^~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 385 ms 30712 KB Output is correct
2 Correct 387 ms 33760 KB Output is correct
3 Correct 264 ms 19768 KB Output is correct
4 Correct 264 ms 34180 KB Output is correct
5 Correct 411 ms 74584 KB Output is correct

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 385 ms 30712 KB Output is correct
2 Correct 387 ms 33760 KB Output is correct
3 Correct 264 ms 19768 KB Output is correct
4 Correct 264 ms 34180 KB Output is correct
5 Correct 411 ms 74584 KB Output is correct
6 Execution timed out 1582 ms 184024 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 385 ms 30712 KB Output is correct
2 Correct 387 ms 33760 KB Output is correct
3 Correct 264 ms 19768 KB Output is correct
4 Correct 264 ms 34180 KB Output is correct
5 Correct 411 ms 74584 KB Output is correct
6 Execution timed out 1582 ms 184024 KB Time limit exceeded
7 Halted 0 ms 0 KB -