Submission #857496


Source Code Expand

Copy
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
#define MOD 1000000007LL
#define endl "\n"
const ll UNDEF = -1;
const ll INF=1e18;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
ll mod_pow(ll a, ll n) {
	ll ret = 1; ll p = a % MOD; while (n) { if (n & 1) ret = ret * p % MOD; p = p * p % MOD; n >>= 1; } return ret; 
}
inline ll mod_inv(ll a) {
	return mod_pow(a,MOD-2);
}
const ll mn=5e5+4;
vector<ll> divs[mn];
void cdiv() {
	for (ll x=1;x<mn;x++) {
		for (ll y=x*2;y<mn;y+=x) {
			divs[y].PB(x);
		}
	}
}
const ll p=101;
ll ht[mn];
ll deninv[mn];
ll ppow[mn];
ll ppowinv[mn];
ll add(ll x, ll y) {return (x+y+MOD)%MOD;}
ll mul(ll x, ll y) {return (x*y)%MOD;}
ll gethash(ll x, ll y) {
	return mul(add(ht[y],-ht[x]),ppowinv[x]);;
}
ll geom(ll n, ll len) {
	ll num=add(1,-ppow[len*n]);
	return mul(num,deninv[len]);
}
ll powup(ll small, ll num, ll len) {
	return mul(small,geom(num,len));
}
bool isgood(ll x, ll y) {
	ll k=y-x;
	ll actual=gethash(x,y);
	for (auto &d:divs[k]) {
		//printf("k:%lld d:%lld\n",k,d);
		//if(d==k) continue;
		ll small=gethash(x,x+d);
		ll num=k/d;
		ll len=d;
		ll big=powup(small, num, len);
		if (big==actual) {
			return false;
		}
	}
	return true;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cdiv();
	{
		ll t=1;
		for (ll x=0;x<mn;x++) {
			ppow[x]=t;
			deninv[x]=mod_inv(add(1,-t));
			ppowinv[x]=mod_inv(t);
			t=(t*p)%MOD;
		}
	}
	string s; cin>>s;
	ll n=s.length();
	ll h=0;
	ht[0]=h;
	ll m=1;
	for (ll x=0;x<n;x++) {
		h+=((s[x]-'a'+1)*m);
		h%=MOD;
		//printf("x:%lld h:%lld\n",x+1,h);
		ht[x+1]=h;
		m=(m*p)%MOD;
	}
	bool same=true;
	for (ll x=1;x<n;x++) {
		if (s[x]!=s[0]) same=false;
	}
	if (same) {
		printf("%lld\n1\n",n);
	}
	else if (isgood(0,n)) {
		printf("1\n1\n");
	}
	else {
		ll ans=0;
		for (ll x=1;x<n;x++) {
			if (isgood(0,x)&&isgood(x,n)) {
				ans++;
			}
		}
		printf("2\n%lld\n",ans);
	}
}

Submission Info

Submission Time
Task F - Best Representation
User LiChenKoh
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2229 Byte
Status TLE
Exec Time 2118 ms
Memory 103324 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 0 / 500
Status
AC × 3
AC × 36
AC × 50
TLE × 15
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 1503 ms 98688 KB
example_02.txt AC 1527 ms 98688 KB
example_03.txt AC 1542 ms 98688 KB
subtask1_01.txt AC 1520 ms 98688 KB
subtask1_02.txt AC 1471 ms 98688 KB
subtask1_03.txt AC 1471 ms 98816 KB
subtask1_04.txt AC 1464 ms 98816 KB
subtask1_05.txt AC 1484 ms 98816 KB
subtask1_06.txt AC 1461 ms 98816 KB
subtask1_07.txt AC 1499 ms 98816 KB
subtask1_08.txt AC 1473 ms 98816 KB
subtask1_09.txt AC 1484 ms 98816 KB
subtask1_10.txt AC 1487 ms 98816 KB
subtask1_11.txt AC 1480 ms 98816 KB
subtask1_12.txt AC 1529 ms 98816 KB
subtask1_13.txt AC 1511 ms 98816 KB
subtask1_14.txt AC 1480 ms 98816 KB
subtask1_15.txt AC 1477 ms 98688 KB
subtask1_16.txt AC 1466 ms 98688 KB
subtask1_17.txt AC 1523 ms 98688 KB
subtask1_18.txt AC 1501 ms 98688 KB
subtask1_19.txt AC 1508 ms 98816 KB
subtask1_20.txt AC 1507 ms 98816 KB
subtask1_21.txt AC 1516 ms 98816 KB
subtask1_22.txt AC 1489 ms 98816 KB
subtask1_23.txt AC 1474 ms 98816 KB
subtask1_24.txt AC 1492 ms 98816 KB
subtask1_25.txt AC 1484 ms 98816 KB
subtask1_26.txt AC 1495 ms 98816 KB
subtask1_27.txt AC 1533 ms 98816 KB
subtask1_28.txt AC 1514 ms 98816 KB
subtask1_29.txt AC 1522 ms 98816 KB
subtask1_30.txt AC 1478 ms 98816 KB
subtask1_31.txt AC 1504 ms 98816 KB
subtask1_32.txt AC 1494 ms 98816 KB
subtask1_33.txt AC 1491 ms 98816 KB
subtask2_01.txt TLE 2075 ms 102292 KB
subtask2_02.txt AC 1514 ms 103196 KB
subtask2_03.txt AC 1495 ms 103324 KB
subtask2_04.txt AC 1509 ms 103324 KB
subtask2_05.txt AC 1510 ms 103324 KB
subtask2_06.txt AC 1522 ms 103324 KB
subtask2_07.txt AC 1537 ms 103324 KB
subtask2_08.txt AC 1500 ms 103324 KB
subtask2_09.txt TLE 2114 ms 103324 KB
subtask2_10.txt TLE 2114 ms 103324 KB
subtask2_11.txt TLE 2117 ms 103324 KB
subtask2_12.txt TLE 2114 ms 103324 KB
subtask2_13.txt AC 1832 ms 103324 KB
subtask2_14.txt AC 1488 ms 103324 KB
subtask2_15.txt AC 1949 ms 103324 KB
subtask2_16.txt AC 1532 ms 103324 KB
subtask2_17.txt AC 1521 ms 103324 KB
subtask2_18.txt AC 1472 ms 103324 KB
subtask2_19.txt TLE 2024 ms 103324 KB
subtask2_20.txt TLE 2111 ms 103324 KB
subtask2_21.txt TLE 2113 ms 102940 KB
subtask2_22.txt TLE 2114 ms 103324 KB
subtask2_23.txt TLE 2117 ms 103324 KB
subtask2_24.txt TLE 2117 ms 102556 KB
subtask2_25.txt TLE 2118 ms 102812 KB
subtask2_26.txt TLE 2114 ms 103068 KB
subtask2_27.txt TLE 2113 ms 102428 KB
subtask2_28.txt AC 1531 ms 101140 KB
subtask2_29.txt TLE 2040 ms 102300 KB