Submission #1554719


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
int A[2][500005];
string S[2];
void Z(int x){
	A[x][0] = S[x].size();
	int i=1,j=0;
	while(i<S[x].size()){
		while(i+j<S[x].size() && S[x][j]==S[x][i+j])j++;
		A[x][i]=j;
		if(j==0){
			i++; continue;
		}
		int k = 1;
		while(i+k<S[x].size() && k+A[x][k]<j) A[x][i+k]=A[x][k],++k;
		i+=k;j-=k;
	}
}
vector<int>v[500005];
bool bad[500005],bad2[500005];
int main(){
	cin >> S[0];
	reverse(S[0].begin(),S[0].end());
	S[1] = S[0];
	reverse(S[0].begin(),S[0].end());
	Z(0); Z(1);
	for(int i=1;i<500005;i++)for(int j=2*i;j<500005;j+=i)v[j].push_back(i);
	for(int i=0;i<S[0].size();i++){
		for(int x=0;x<v[i+1].size();x++){
			int a = v[i+1][x];
			if(A[0][a] >= i+1-a){
				bad[i] = 1; break;
			}
		}
	}
	for(int i=0;i<S[1].size();i++){
		for(int x=0;x<v[i+1].size();x++){
			int a = v[i+1][x];
			if(A[1][a] >= i+1-a){
				bad2[i] = 1; break;
			}
		}
	}
	if(!bad[S[0].size()-1]){
		cout << 1 << endl << 1 << endl;
	}
	else{
	    int ans=0;
		for(int i=1;i<S[0].size();i++){
			if(!bad[i-1] && !bad2[S[0].size()-i-1]) ans++;
		}
		if(!ans) cout << S[0].size() << endl << 1 << endl;
		else cout << 2 << endl << ans << endl;
	}
}

Submission Info

Submission Time
Task F - Best Representation
User IH19980412
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1223 Byte
Status AC
Exec Time 609 ms
Memory 61732 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 500 / 500
Status
AC × 3
AC × 36
AC × 65
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt
All example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt
Case Name Status Exec Time Memory
example_01.txt AC 534 ms 59520 KB
example_02.txt AC 521 ms 59520 KB
example_03.txt AC 518 ms 59520 KB
subtask1_01.txt AC 526 ms 59520 KB
subtask1_02.txt AC 529 ms 59520 KB
subtask1_03.txt AC 528 ms 59520 KB
subtask1_04.txt AC 520 ms 59520 KB
subtask1_05.txt AC 528 ms 59520 KB
subtask1_06.txt AC 523 ms 59520 KB
subtask1_07.txt AC 498 ms 59520 KB
subtask1_08.txt AC 512 ms 59520 KB
subtask1_09.txt AC 493 ms 59520 KB
subtask1_10.txt AC 470 ms 59520 KB
subtask1_11.txt AC 510 ms 59520 KB
subtask1_12.txt AC 517 ms 59520 KB
subtask1_13.txt AC 503 ms 59520 KB
subtask1_14.txt AC 498 ms 59520 KB
subtask1_15.txt AC 499 ms 59520 KB
subtask1_16.txt AC 495 ms 59520 KB
subtask1_17.txt AC 492 ms 59520 KB
subtask1_18.txt AC 483 ms 59520 KB
subtask1_19.txt AC 483 ms 59520 KB
subtask1_20.txt AC 488 ms 59520 KB
subtask1_21.txt AC 500 ms 59648 KB
subtask1_22.txt AC 539 ms 59520 KB
subtask1_23.txt AC 512 ms 59520 KB
subtask1_24.txt AC 477 ms 59520 KB
subtask1_25.txt AC 510 ms 59520 KB
subtask1_26.txt AC 496 ms 59520 KB
subtask1_27.txt AC 480 ms 59520 KB
subtask1_28.txt AC 481 ms 59520 KB
subtask1_29.txt AC 485 ms 59520 KB
subtask1_30.txt AC 529 ms 59520 KB
subtask1_31.txt AC 471 ms 59520 KB
subtask1_32.txt AC 543 ms 59520 KB
subtask1_33.txt AC 514 ms 59520 KB
subtask2_01.txt AC 576 ms 61732 KB
subtask2_02.txt AC 538 ms 61700 KB
subtask2_03.txt AC 588 ms 61188 KB
subtask2_04.txt AC 546 ms 61188 KB
subtask2_05.txt AC 543 ms 61700 KB
subtask2_06.txt AC 547 ms 61188 KB
subtask2_07.txt AC 571 ms 61188 KB
subtask2_08.txt AC 566 ms 60804 KB
subtask2_09.txt AC 601 ms 60804 KB
subtask2_10.txt AC 570 ms 60804 KB
subtask2_11.txt AC 565 ms 60804 KB
subtask2_12.txt AC 562 ms 60804 KB
subtask2_13.txt AC 572 ms 61700 KB
subtask2_14.txt AC 605 ms 61700 KB
subtask2_15.txt AC 589 ms 61700 KB
subtask2_16.txt AC 541 ms 61700 KB
subtask2_17.txt AC 574 ms 61188 KB
subtask2_18.txt AC 544 ms 61188 KB
subtask2_19.txt AC 581 ms 60932 KB
subtask2_20.txt AC 576 ms 60932 KB
subtask2_21.txt AC 536 ms 60676 KB
subtask2_22.txt AC 553 ms 61700 KB
subtask2_23.txt AC 609 ms 61700 KB
subtask2_24.txt AC 563 ms 61188 KB
subtask2_25.txt AC 561 ms 61316 KB
subtask2_26.txt AC 571 ms 61572 KB
subtask2_27.txt AC 540 ms 61188 KB
subtask2_28.txt AC 538 ms 60036 KB
subtask2_29.txt AC 547 ms 60292 KB