Submission #857269


Source Code Expand

Copy
#include <vector>
#include <iostream>
#include <unordered_map>
#include <map>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <string>
#include <sstream>
using namespace std;

#ifndef MDEBUG
#define NDEBUG
#endif

#define x first
#define y second
#define ll long long
#define d double
#define ld long double
#define pii pair<int,int>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define pss pair<string,string>
#define psi pair<string,int>
#define pis pair<int,string>
#define psl pair<string,ll>
#define pls pair<ll,string>
#define wh(x) (x).begin(),(x).end()
#define ri(x) int x;cin>>x;
#define rii(x,y) int x,y;cin>>x>>y;
#define rl(x) ll x;cin>>x;
#define rv(v) for(auto&_cinv:v) cin>>_cinv;
#define wv(v) for(auto&_coutv:v) cout << _coutv << ' '; cout << endl;
#define ev(v) for(auto&_cerrv:v) cerr << _cerrv << ' '; cerr << endl;
#define MOD 1000000007

namespace std { 
template<typename T,typename U>struct hash<pair<T,U>>{hash<T>t;hash<U>u;size_t operator()(const pair<T,U>&p)const{return t(p.x)^(u(p.y)<<7);}};
}
// auto fraclt = [](auto&a,auto&b) { return (ll)a.x * b.y < (ll)b.x * a.y; };
template<typename T,typename F>T bsh(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){l=m+1;r=m;}else{h=m-1;}}return r;}
template<typename T,typename F>T bsl(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){h=m-1;r=m;}else{l=m+1;}}return r;}
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }
template<typename T> void fracn(pair<T,T>&a) {auto g=gcd(a.x,a.y);a.x/=g;a.y/=g;}
template<typename T> struct Index { int operator[](const T&t){auto i=m.find(t);return i!=m.end()?i->y:m[t]=m.size();}int s(){return m.size();} unordered_map<T,int> m; };


pii isgood(string W) {
    int N = W.size();

    bool diff = false;
    for (int i = 1; i < N && !diff; i++) {
        diff |= (W[0] != W[i]); 
    }
    if (!diff) return {N,1};
    
    for (int i = 2; i < N; i++) {
        if (N % i != 0) continue;
        bool diff = false;
        for (int j = i; j < N && !diff; j+=i) {
            for (int k = 0; k < i && !diff; k++) {
                diff |= W[k] != W[j+k];
            }
        }
        if (!diff) {
            int g = 2*i-4;
            for (int j = 2; j < i; j++) {
                pii a = isgood(W.substr(0,j));
                if (a.x == 1) --g;
            }
            for (int j = 2; j < i; j++) {
                pii a = isgood(W.substr(N-j,N));
                if (a.x == 1) --g;
            }


            if (N/i == 2) {
                return{2, N-1-g};
            } else {
                return{2, N-(N/i)-g}; 
            }
        }
    }
    return {1,1};
}

int main(int,char**) {
    ios_base::sync_with_stdio(false);

    string W; cin >> W;
    pii x = isgood(W);
    cout << x.x << endl << x.y << endl;
}

Submission Info

Submission Time
Task F - Best Representation
User majk
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2978 Byte
Status WA
Exec Time 2105 ms
Memory 1308 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 400 0 / 500
Status
AC × 3
AC × 35
WA × 1
AC × 55
WA × 1
TLE × 9
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 4 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 WA 6 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 73 ms 256 KB
subtask1_12.txt AC 73 ms 256 KB
subtask1_13.txt AC 46 ms 256 KB
subtask1_14.txt AC 37 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 54 ms 256 KB
subtask1_26.txt AC 46 ms 256 KB
subtask1_27.txt AC 8 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 13 ms 256 KB
subtask2_01.txt TLE 2101 ms 1172 KB
subtask2_02.txt AC 9 ms 1308 KB
subtask2_03.txt AC 13 ms 1308 KB
subtask2_04.txt AC 12 ms 1308 KB
subtask2_05.txt AC 9 ms 1308 KB
subtask2_06.txt AC 63 ms 1308 KB
subtask2_07.txt AC 12 ms 1308 KB
subtask2_08.txt AC 12 ms 1308 KB
subtask2_09.txt TLE 2101 ms 1308 KB
subtask2_10.txt TLE 2101 ms 1308 KB
subtask2_11.txt TLE 2105 ms 1308 KB
subtask2_12.txt TLE 2101 ms 1308 KB
subtask2_13.txt AC 9 ms 1308 KB
subtask2_14.txt AC 12 ms 1308 KB
subtask2_15.txt AC 9 ms 1308 KB
subtask2_16.txt AC 12 ms 1308 KB
subtask2_17.txt AC 12 ms 1308 KB
subtask2_18.txt AC 12 ms 1308 KB
subtask2_19.txt TLE 2105 ms 1308 KB
subtask2_20.txt TLE 2101 ms 1308 KB
subtask2_21.txt TLE 2105 ms 1308 KB
subtask2_22.txt AC 16 ms 1308 KB
subtask2_23.txt AC 12 ms 1308 KB
subtask2_24.txt AC 23 ms 1180 KB
subtask2_25.txt AC 10 ms 1308 KB
subtask2_26.txt AC 12 ms 1308 KB
subtask2_27.txt AC 11 ms 1180 KB
subtask2_28.txt AC 10 ms 916 KB
subtask2_29.txt TLE 2101 ms 1180 KB