Submission #856581


Source Code Expand

Copy
#include <bits/stdc++.h> 

using namespace std;

typedef long long ll; 
typedef pair<int, int> pii;

#define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)

int ways[510000];
int dist[510000];

int okf[510000];
int okb[510000];
char s[510000];
char *p; 
int pos[510000]; 
int n,m; 

void func(){
     int i, j=-1;
     pos[0]=-1;
     for( i=1 ; i<m ; i++ ){
          while( j>=0 && p[j+1]!=p[i] )
                 j=pos[j];
          if( p[j+1]==p[i] )
              j++;
          pos[i]=j;
     }     
}

bool ok(int i, int j) {
	m = j-i+1;
	p=s+i;
	func();

	int period = (m - pos[m-1] - 1);
	return period == m || (m % period != 0);
}

int main() {
	scanf("%s", s);
	p = s;
	m = strlen(p);
	n = m;

	reverse(s,s+m);
	func();

	for (int i = 0; i < m; i++) {
		int period = (i+1) - pos[i] - 1;
		okb[i] = (period == i+1) || ((i+1) % period != 0);
	}

	reverse(s,s+m);
	func();

	for (int i = 0; i < m; i++) {
		int period = (i+1) - pos[i] - 1;
		okf[i] = (period == i+1) || ((i+1) % period != 0);
	}


	int period = m - pos[m-1] - 1;
	if (period == 1) {
		printf("%d\n",m);
		printf("1\n");
	}
	else if (period < m && m % period == 0) {
		int ans = 0;
		for (int i = 0; i < m-1; i++) {
			if (okf[i] && okb[m-i-2]) ans++;
		}
		printf("2\n");
		printf("%d\n", ans);
	}
	else {
		printf("1\n");
		printf("1\n");
	}

	/*printf("\n");

	ways[0] = 1;
	dist[0] = 0;

	for (int j = 0; j < n; j++) {
		dist[j+1] = -1;

		for (int i = 0; i <= j; i++) {
			if (ok(i,j)) {
				if (dist[j+1] == -1 || dist[j+1] > dist[i]+1) {
					dist[j+1] = dist[i]+1;
					ways[j+1] = 0;
				}
				if (dist[j+1] == dist[i]+1) {
					ways[j+1] = (ways[j+1] + ways[i]) % 1000000007;
				}
			}
		}
	}

	printf("%d\n%d\n", dist[n], ways[n]);*/
}

Submission Info

Submission Time
Task F - Best Representation
User ffao
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1819 Byte
Status AC
Exec Time 29 ms
Memory 6656 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:42:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s);
                ^

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 6 ms 256 KB
example_02.txt AC 4 ms 256 KB
example_03.txt AC 4 ms 256 KB
subtask1_01.txt AC 4 ms 256 KB
subtask1_02.txt AC 4 ms 256 KB
subtask1_03.txt AC 4 ms 256 KB
subtask1_04.txt AC 4 ms 256 KB
subtask1_05.txt AC 4 ms 256 KB
subtask1_06.txt AC 4 ms 256 KB
subtask1_07.txt AC 4 ms 256 KB
subtask1_08.txt AC 4 ms 256 KB
subtask1_09.txt AC 4 ms 256 KB
subtask1_10.txt AC 4 ms 256 KB
subtask1_11.txt AC 4 ms 256 KB
subtask1_12.txt AC 4 ms 256 KB
subtask1_13.txt AC 4 ms 256 KB
subtask1_14.txt AC 4 ms 256 KB
subtask1_15.txt AC 4 ms 256 KB
subtask1_16.txt AC 4 ms 256 KB
subtask1_17.txt AC 4 ms 256 KB
subtask1_18.txt AC 4 ms 256 KB
subtask1_19.txt AC 4 ms 256 KB
subtask1_20.txt AC 4 ms 256 KB
subtask1_21.txt AC 4 ms 256 KB
subtask1_22.txt AC 4 ms 256 KB
subtask1_23.txt AC 4 ms 256 KB
subtask1_24.txt AC 4 ms 256 KB
subtask1_25.txt AC 4 ms 256 KB
subtask1_26.txt AC 4 ms 256 KB
subtask1_27.txt AC 5 ms 256 KB
subtask1_28.txt AC 4 ms 256 KB
subtask1_29.txt AC 4 ms 256 KB
subtask1_30.txt AC 4 ms 256 KB
subtask1_31.txt AC 4 ms 256 KB
subtask1_32.txt AC 4 ms 256 KB
subtask1_33.txt AC 4 ms 256 KB
subtask2_01.txt AC 22 ms 5248 KB
subtask2_02.txt AC 27 ms 6528 KB
subtask2_03.txt AC 24 ms 6528 KB
subtask2_04.txt AC 23 ms 6528 KB
subtask2_05.txt AC 25 ms 6656 KB
subtask2_06.txt AC 25 ms 6656 KB
subtask2_07.txt AC 23 ms 6656 KB
subtask2_08.txt AC 27 ms 6656 KB
subtask2_09.txt AC 26 ms 6656 KB
subtask2_10.txt AC 27 ms 6656 KB
subtask2_11.txt AC 27 ms 6656 KB
subtask2_12.txt AC 24 ms 6656 KB
subtask2_13.txt AC 27 ms 6656 KB
subtask2_14.txt AC 25 ms 6656 KB
subtask2_15.txt AC 26 ms 6656 KB
subtask2_16.txt AC 29 ms 6656 KB
subtask2_17.txt AC 25 ms 6656 KB
subtask2_18.txt AC 25 ms 6656 KB
subtask2_19.txt AC 25 ms 6656 KB
subtask2_20.txt AC 27 ms 6656 KB
subtask2_21.txt AC 24 ms 6144 KB
subtask2_22.txt AC 26 ms 6656 KB
subtask2_23.txt AC 26 ms 6656 KB
subtask2_24.txt AC 23 ms 5632 KB
subtask2_25.txt AC 25 ms 5888 KB
subtask2_26.txt AC 25 ms 6272 KB
subtask2_27.txt AC 22 ms 5376 KB
subtask2_28.txt AC 15 ms 3584 KB
subtask2_29.txt AC 21 ms 5248 KB