Submission #856368


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())
string str;
int n,k;
int ran[500005];
int tmp[500005];
int sa[500005];
 
bool compare_sa(int i,int j)
{
	if(ran[i] != ran[j]) return ran[i] < ran[j];
	else
	{
		int ri = i+k<=n ? ran[i+k]: -1;
		int rj = j+k<=n ? ran[j+k]: -1;
		
		return ri < rj;
	}
}
 
void constuct_sa(string S)
{
	for(int i=0;i<=n;i++)
	{
		sa[i] = i;
		ran[i] = i<n?S[i]:-1;
	}
	
	for(k=1;k<=n;k*=2)
	{
		sort(sa,sa+n+1,compare_sa);
		
		tmp[sa[0]] = 0;
		for(int i=1;i<=n;i++)
		{
			tmp[sa[i]] = tmp[sa[i-1]] + compare_sa(sa[i-1],sa[i]);
		}
		for(int i=0;i<=n;i++)
		{
			ran[i] = tmp[i];
		}
	}
}
int lcp[500005];
void construct_lcp(string S)
{
	int n = S.size();
	for(int i=0;i<=n;i++) ran[sa[i]] = i;
	
	int h = 0;
	lcp[0] = 0;
	
	for(int i=0;i<n;i++)
	{
		int j = sa[ran[i]-1];
		
		if(h) h--;
		for(;j+h<n && i+h<n;h++)
		{
			if(S[j+h] != S[i+h]) break;
		}
		lcp[ran[i]-1] = h;
	}
}
int seg[(1<<20)];
void update(int k,int a){
	k+=(1<<19)-1; seg[k]=a;
	while(k>0){
		k=(k-1)/2;
		seg[k]=min(seg[k*2+1],seg[k*2+2]);
	}
}
int query(int a,int b,int k,int l,int r){
	if(r<a || b<l) return INF;
	if(a<=l && r<=b) return seg[k];
	else{
		int vl=query(a,b,k*2+1,l,(l+r)/2);
		int vr=query(a,b,k*2+2,(l+r)/2+1,r);
		return min(vl,vr);
	}
}
vector<int>divb[500005];
int main(){
	cin >> str; n = str.size();
	if(n<100000){
		constuct_sa(str); construct_lcp(str);
	}
	bool as = 0,rep = 0; int M = INF;
	for(int i=1;i<n;i++){
		if(n%i != 0) continue;
		for(int j=0;j<i;j++){
			char cur = str[j];
			for(int k=j+i;k<n;k+=i){
				if(cur != str[k]) goto bad;
			}
		}
		rep = 1; M = min(M,i); if(i==1) as = 1; bad:;
	}
	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;
	}
	if(n>=100000){
		cout << 2 << endl << n-n/M << endl; return 0;
	}
	for(int i=0;i<n;i++){
		update(i,lcp[i]);
	}
	
	{
		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 a = ran[0];
				int b = ran[divb[i][j]];
				if(a > b) swap(a,b);
				
				if(query(a,b-1,0,0,(1<<19)-1) >= i-divb[i][j]){
					goto bad1;
				}
			}
			for(int j=0;j<divb[n-i].size();j++){
				int a = ran[i];
				int b = ran[i+divb[n-i][j]];
				if(a > b) swap(a,b);
				
				if(query(a,b-1,0,0,(1<<19)-1) >= n-i-divb[n-i][j]){
					goto bad1;
				}
			}
			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 3432 Byte
Status WA
Exec Time 1192 ms
Memory 56324 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 0 / 500
Status
AC × 3
AC × 36
AC × 53
WA × 12
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 925 ms 55808 KB
example_02.txt AC 972 ms 55936 KB
example_03.txt AC 952 ms 55808 KB
subtask1_01.txt AC 947 ms 55936 KB
subtask1_02.txt AC 941 ms 55808 KB
subtask1_03.txt AC 941 ms 55936 KB
subtask1_04.txt AC 937 ms 55936 KB
subtask1_05.txt AC 977 ms 55936 KB
subtask1_06.txt AC 982 ms 55936 KB
subtask1_07.txt AC 935 ms 55936 KB
subtask1_08.txt AC 931 ms 55936 KB
subtask1_09.txt AC 926 ms 55936 KB
subtask1_10.txt AC 947 ms 55936 KB
subtask1_11.txt AC 962 ms 56064 KB
subtask1_12.txt AC 960 ms 56064 KB
subtask1_13.txt AC 970 ms 56064 KB
subtask1_14.txt AC 952 ms 56064 KB
subtask1_15.txt AC 933 ms 55808 KB
subtask1_16.txt AC 925 ms 55808 KB
subtask1_17.txt AC 927 ms 55808 KB
subtask1_18.txt AC 926 ms 55808 KB
subtask1_19.txt AC 948 ms 56064 KB
subtask1_20.txt AC 956 ms 55936 KB
subtask1_21.txt AC 943 ms 56064 KB
subtask1_22.txt AC 931 ms 55936 KB
subtask1_23.txt AC 927 ms 55936 KB
subtask1_24.txt AC 933 ms 55936 KB
subtask1_25.txt AC 942 ms 56064 KB
subtask1_26.txt AC 950 ms 56064 KB
subtask1_27.txt AC 957 ms 56064 KB
subtask1_28.txt AC 967 ms 56064 KB
subtask1_29.txt AC 960 ms 56064 KB
subtask1_30.txt AC 950 ms 56064 KB
subtask1_31.txt AC 954 ms 56064 KB
subtask1_32.txt AC 957 ms 56064 KB
subtask1_33.txt AC 952 ms 56064 KB
subtask2_01.txt WA 951 ms 56196 KB
subtask2_02.txt AC 1192 ms 56324 KB
subtask2_03.txt AC 965 ms 56324 KB
subtask2_04.txt AC 952 ms 56324 KB
subtask2_05.txt AC 999 ms 56324 KB
subtask2_06.txt AC 1005 ms 56324 KB
subtask2_07.txt AC 970 ms 56324 KB
subtask2_08.txt AC 1007 ms 56324 KB
subtask2_09.txt WA 950 ms 56324 KB
subtask2_10.txt WA 965 ms 56324 KB
subtask2_11.txt WA 971 ms 56324 KB
subtask2_12.txt WA 976 ms 56324 KB
subtask2_13.txt AC 1003 ms 56324 KB
subtask2_14.txt AC 961 ms 56324 KB
subtask2_15.txt WA 977 ms 56324 KB
subtask2_16.txt AC 951 ms 56324 KB
subtask2_17.txt AC 952 ms 56324 KB
subtask2_18.txt AC 953 ms 56324 KB
subtask2_19.txt WA 950 ms 56324 KB
subtask2_20.txt WA 968 ms 56324 KB
subtask2_21.txt WA 962 ms 56324 KB
subtask2_22.txt WA 963 ms 56324 KB
subtask2_23.txt WA 1043 ms 56324 KB
subtask2_24.txt AC 951 ms 56324 KB
subtask2_25.txt AC 963 ms 56324 KB
subtask2_26.txt AC 983 ms 56324 KB
subtask2_27.txt AC 966 ms 56196 KB
subtask2_28.txt AC 940 ms 56068 KB
subtask2_29.txt WA 947 ms 56196 KB