Submission #857180


Source Code Expand

Copy
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <cassert>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
char str[1][500005];
int n,k;
vector<int>divb[500005];
int num[1][20][500005];
vector<int>G[500005];
void make(int p){
	for(int i=0;i<n;i++) num[p][0][i] = 1 + str[p][i]-'a'; 
	for(int i=1;i<20;i++){
		int nxtt = 1;
		for(int j=0;j<n;j++){
			if(j+(1<<i) > n) continue;
			ll hoge = 1LL* num[p][i-1][j] * 299833 + 1LL* num[p][i-1][j+(1<<(i-1))];
			hoge %= 500005; //cout << i << " " << j << " " << hoge << endl;
			if(G[hoge].empty()){
				num[p][i][j] = nxtt++;
				G[hoge].pb(j);
			}
			else{
				for(int ii=0;ii<G[hoge].size();ii++){
					int x = G[hoge][ii];
					if(num[p][i-1][j] == num[p][i-1][x] && num[p][i-1][j+(1<<(i-1))] == num[p][i-1][x+(1<<(i-1))]){
						num[p][i][j] = num[p][i][x];
						goto nxt1;
					}
				}
				num[p][i][j] = nxtt++;G[hoge].pb(j); nxt1:;
			}
		}
		for(int i=0;i<500005;i++) G[i].clear();
	}
}
int main(){
	scanf("%s",&str[0]); n = strlen(str[0]);
	make(0); 
	bool as = 0,rep = 0; int M = INF;
	for(int i=1;i<n;i++){
		if(n%i != 0) continue;
		int x = (n-i);
		int a = 0,b = i;
		for(int j=0;j<20;j++){
			if(((x>>j)&1)){
				if(num[0][j][a] == num[0][j][b]){
					a += (1<<j);
					b += (1<<j);
				}
				else goto nxt2;
			}
		}
		rep = 1; if(i == 1) as = 1; nxt2:;
	}
	for(int i=1;i<=500000;i++){
		for(int j=i+i;j<=500000;j+=i){
			divb[j].pb(i);
		}
	}
	
	if(as){
		cout << n << endl << 1 << endl; return 0;
	}
	if(!rep){
		cout << 1 << endl << 1 << endl; return 0;
	}
	{
		cout << 2 << endl;
		int ret = 0;
		for(int i=1;i<=n-1;i++){
			//pre=i back=n-i
			for(int j=0;j<divb[i].size();j++){
				int x = (i-divb[i][j]);
				int a = 0,b = divb[i][j];
				for(int j=0;j<20;j++){
					if(((x>>j)&1)){
						if(num[0][j][a] == num[0][j][b]){
							a += (1<<j);
							b += (1<<j);
						}
						else goto nxt;
					}
				}
				goto bad1; nxt:;
			}
			for(int j=0;j<divb[n-i].size();j++){
				int x = (n-i-divb[n-i][j]);
				int a = i,b = i+divb[n-i][j];
				
				for(int j=0;j<20;j++){
					if(((x>>j)&1)){
						if(num[0][j][a] == num[0][j][b]){
							a += (1<<j);
							b += (1<<j);
						}
						else goto nxt3;
					}
				}
				goto bad1; nxt3:;
			}
			ret++; bad1:;
		}
		assert(ret) ; cout << ret << endl;
	}
}

Submission Info

Submission Time
Task F - Best Representation
User IH19980412
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3099 Byte
Status TLE
Exec Time 2113 ms
Memory 118784 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:20: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘char (*)[500005]’ [-Wformat=]
  scanf("%s",&str[0]); n = strlen(str[0]);
                    ^
./Main.cpp:66:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",&str[0]); n = strlen(str[0]);
                     ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 0 / 500
Status
AC × 3
AC × 36
AC × 61
TLE × 4
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 1023 ms 67584 KB
example_02.txt AC 982 ms 67584 KB
example_03.txt AC 985 ms 67584 KB
subtask1_01.txt AC 982 ms 67584 KB
subtask1_02.txt AC 970 ms 67584 KB
subtask1_03.txt AC 971 ms 67712 KB
subtask1_04.txt AC 970 ms 67840 KB
subtask1_05.txt AC 971 ms 67840 KB
subtask1_06.txt AC 972 ms 67840 KB
subtask1_07.txt AC 974 ms 67840 KB
subtask1_08.txt AC 976 ms 67840 KB
subtask1_09.txt AC 1020 ms 67840 KB
subtask1_10.txt AC 1150 ms 67840 KB
subtask1_11.txt AC 1056 ms 67968 KB
subtask1_12.txt AC 1005 ms 67968 KB
subtask1_13.txt AC 979 ms 67968 KB
subtask1_14.txt AC 1004 ms 68480 KB
subtask1_15.txt AC 986 ms 67584 KB
subtask1_16.txt AC 973 ms 67584 KB
subtask1_17.txt AC 977 ms 67584 KB
subtask1_18.txt AC 986 ms 67584 KB
subtask1_19.txt AC 1012 ms 67840 KB
subtask1_20.txt AC 974 ms 67840 KB
subtask1_21.txt AC 981 ms 67840 KB
subtask1_22.txt AC 974 ms 67840 KB
subtask1_23.txt AC 982 ms 67840 KB
subtask1_24.txt AC 989 ms 67840 KB
subtask1_25.txt AC 981 ms 67968 KB
subtask1_26.txt AC 976 ms 67968 KB
subtask1_27.txt AC 985 ms 67840 KB
subtask1_28.txt AC 996 ms 67840 KB
subtask1_29.txt AC 992 ms 67840 KB
subtask1_30.txt AC 999 ms 67840 KB
subtask1_31.txt AC 998 ms 67840 KB
subtask1_32.txt AC 999 ms 67840 KB
subtask1_33.txt AC 991 ms 68096 KB
subtask2_01.txt AC 1637 ms 103680 KB
subtask2_02.txt AC 1188 ms 103168 KB
subtask2_03.txt AC 1181 ms 103168 KB
subtask2_04.txt AC 1191 ms 103168 KB
subtask2_05.txt AC 1175 ms 103168 KB
subtask2_06.txt AC 1168 ms 103168 KB
subtask2_07.txt AC 1181 ms 103168 KB
subtask2_08.txt AC 1298 ms 111616 KB
subtask2_09.txt AC 1937 ms 116992 KB
subtask2_10.txt AC 1932 ms 116736 KB
subtask2_11.txt AC 1888 ms 116224 KB
subtask2_12.txt TLE 2113 ms 118784 KB
subtask2_13.txt AC 1345 ms 103168 KB
subtask2_14.txt AC 1195 ms 103168 KB
subtask2_15.txt AC 1432 ms 103168 KB
subtask2_16.txt AC 1171 ms 103168 KB
subtask2_17.txt AC 1200 ms 103168 KB
subtask2_18.txt AC 1189 ms 103168 KB
subtask2_19.txt TLE 2112 ms 115712 KB
subtask2_20.txt AC 1990 ms 115328 KB
subtask2_21.txt TLE 2111 ms 106752 KB
subtask2_22.txt TLE 2111 ms 103296 KB
subtask2_23.txt AC 1896 ms 103296 KB
subtask2_24.txt AC 1466 ms 98048 KB
subtask2_25.txt AC 1481 ms 99328 KB
subtask2_26.txt AC 1539 ms 101632 KB
subtask2_27.txt AC 1442 ms 96256 KB
subtask2_28.txt AC 1265 ms 92032 KB
subtask2_29.txt AC 1691 ms 106880 KB