Contest Duration: - (local time) (100 minutes) Back to Home

Submission #856908

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[2];
int n,k;
vector<int>divb[500005];
ll num[2][20][500005];
vector<int>G[1000005];
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 = num[p][i-1][j] * 799833 + num[p][i-1][j+(1<<(i-1))];
hoge %= 1000005; //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++; nxt1:;
G[hoge].pb(j);
}
}
for(int i=0;i<1000005;i++) G[i].clear();
}
}
int main(){
cin >> str[0]; n = str[0].size();
reverse(str[0].begin(),str[0].end()); str[1] = str[0];
reverse(str[0].begin(),str[0].end());
make(0); make(1);
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;
}
}
}
for(int j=0;j<divb[n-i].size();j++){
int x = (n-i-divb[n-i][j]);
int a = 0,b = divb[n-i][j];

for(int j=0;j<20;j++){
if(((x>>j)&1)){
if(num[1][j][a] == num[1][j][b]){
a += (1<<j);
b += (1<<j);
}
else goto nxt3;
}
}
}
}
assert(ret) ; cout << ret << endl;
}
}```

#### Submission Info

Submission Time 2016-08-28 22:28:05+0900 F - Best Representation IH19980412 C++14 (GCC 5.4.1) 400 3188 Byte TLE 2128 ms 284532 KB

#### Judge Result

Score / Max Score 0 / 0 400 / 400 0 / 500
Status
 AC × 3
 AC × 36
 AC × 49 TLE × 16
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt
Case Name Status Exec Time Memory
example_01.txt AC 1096 ms 79232 KB
example_02.txt AC 1092 ms 79360 KB
example_03.txt AC 1103 ms 79360 KB
subtask1_01.txt AC 1089 ms 79360 KB
subtask1_02.txt AC 1087 ms 79360 KB
subtask1_03.txt AC 1096 ms 79488 KB
subtask1_04.txt AC 1093 ms 80128 KB
subtask1_05.txt AC 1102 ms 80128 KB
subtask1_06.txt AC 1104 ms 80128 KB
subtask1_07.txt AC 1126 ms 80128 KB
subtask1_08.txt AC 1110 ms 80128 KB
subtask1_09.txt AC 1143 ms 80128 KB
subtask1_10.txt AC 1107 ms 80384 KB
subtask1_11.txt AC 1128 ms 80512 KB
subtask1_12.txt AC 1107 ms 80512 KB
subtask1_13.txt AC 1116 ms 80384 KB
subtask1_14.txt AC 1156 ms 80768 KB
subtask1_15.txt AC 1129 ms 79232 KB
subtask1_16.txt AC 1097 ms 79360 KB
subtask1_17.txt AC 1087 ms 79360 KB
subtask1_18.txt AC 1105 ms 79360 KB
subtask1_19.txt AC 1104 ms 80128 KB
subtask1_20.txt AC 1134 ms 80128 KB
subtask1_21.txt AC 1109 ms 80128 KB
subtask1_22.txt AC 1124 ms 80128 KB
subtask1_23.txt AC 1137 ms 80128 KB
subtask1_24.txt AC 1120 ms 80128 KB
subtask1_25.txt AC 1166 ms 80384 KB
subtask1_26.txt AC 1127 ms 80512 KB
subtask1_27.txt AC 1115 ms 80256 KB
subtask1_28.txt AC 1118 ms 80256 KB
subtask1_29.txt AC 1103 ms 80256 KB
subtask1_30.txt AC 1100 ms 80384 KB
subtask1_31.txt AC 1096 ms 80384 KB
subtask1_32.txt AC 1156 ms 80384 KB
subtask1_33.txt AC 1111 ms 80384 KB
subtask2_01.txt TLE 2123 ms 232052 KB
subtask2_02.txt AC 1680 ms 224248 KB
subtask2_03.txt AC 1702 ms 226168 KB
subtask2_04.txt AC 1728 ms 226168 KB
subtask2_05.txt AC 1676 ms 224504 KB
subtask2_06.txt AC 1722 ms 226424 KB
subtask2_07.txt AC 1689 ms 226424 KB
subtask2_08.txt TLE 2127 ms 277876 KB
subtask2_09.txt TLE 2128 ms 284532 KB
subtask2_10.txt TLE 2128 ms 283124 KB
subtask2_11.txt TLE 2127 ms 267380 KB
subtask2_12.txt TLE 2116 ms 151940 KB
subtask2_13.txt AC 1806 ms 224544 KB
subtask2_14.txt AC 1673 ms 224544 KB
subtask2_15.txt AC 1936 ms 226416 KB
subtask2_16.txt AC 1691 ms 226416 KB
subtask2_17.txt AC 1714 ms 229056 KB
subtask2_18.txt AC 1788 ms 229056 KB
subtask2_19.txt TLE 2126 ms 260596 KB
subtask2_20.txt TLE 2127 ms 274424 KB
subtask2_21.txt TLE 2122 ms 225440 KB
subtask2_22.txt TLE 2125 ms 254600 KB
subtask2_23.txt TLE 2125 ms 254600 KB
subtask2_24.txt TLE 2124 ms 240772 KB
subtask2_25.txt TLE 2127 ms 238468 KB
subtask2_26.txt TLE 2126 ms 260228 KB
subtask2_27.txt TLE 2123 ms 226436 KB
subtask2_28.txt AC 1839 ms 181372 KB
subtask2_29.txt TLE 2125 ms 245756 KB