Submission #856724


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <ctype.h>
#include <deque>
#include <queue>
#include <cstring>
#include <set>
#include <list>
#include <map>
#include <random>
#include <unordered_map>
#include <stdio.h>

using namespace std;

typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<bool> vb;
typedef std::vector<string> vs;
typedef std::vector<double> vd;
typedef std::vector<long long> vll;
typedef std::vector<std::vector<int> > vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef std::vector<std::pair<int, int> > vpi;
typedef vector<vpi> vvpi;
typedef std::pair<int, int> pi;
typedef std::pair<ll, ll> pll;
typedef std::vector<pll> vpll;

const long long mod = 1000000007;

#define all(c) (c).begin(),(c).end()
#define sz(c) (int)(c).size()
#define forn(i, a, b) for(int i = a; i < b; i++)

#define pb push_back
#define mp make_pair

char incaa[505000];

vector<int> prefix_function (string s) {
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}

int main()
{

//    gets(incaa);
//    string s(incaa);
    string s;
    getline(cin, s);
    int n = s.size();
    bool f1=true;
    forn(i,0,n) {
        if(s[i]!=s[0]) f1=false;
    }
    if(f1) {
        cout<<n<<endl;
        cout<<1<<endl;
        return 0;
    }
    vi pf1 = prefix_function(s);
    reverse(all(s));
    vi pf2 = prefix_function(s);
    
    int l1 = n;
    int sl1 = pf1[n-1];
    int dl1 = n-sl1;
    if(sl1 == 0 || l1%dl1 !=0) {
        cout<<1<<endl<<1<<endl;
        return 0;
    }
    
    cout<<2<<endl;
    
    
    
    int cnt =0 ;
    forn(i,1,n) {
        int l = i;
        int r = n-i;
        int sl = pf1[l-1];
        int sr = pf2[r-1];
        int dl = l - sl;
        int dr = r - sr;
        if((l%dl == 0 && sl>0)|| (r%dr ==0 &&sr>0)) continue;
        cnt++;
    }
    cout<<cnt<<endl;
    
    
    
    
    
}

Submission Info

Submission Time
Task F - Best Representation
User Vercingetorix
Language C++14 (GCC 5.4.1)
Score 900
Code Size 2200 Byte
Status AC
Exec Time 58 ms
Memory 5148 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 500 / 500
Status
AC × 3
AC × 36
AC × 65
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 AC 4 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 4 ms 256 KB
subtask1_12.txt AC 4 ms 256 KB
subtask1_13.txt AC 4 ms 256 KB
subtask1_14.txt AC 4 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 4 ms 256 KB
subtask1_26.txt AC 4 ms 256 KB
subtask1_27.txt AC 4 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 4 ms 256 KB
subtask2_01.txt AC 46 ms 4100 KB
subtask2_02.txt AC 32 ms 900 KB
subtask2_03.txt AC 51 ms 5148 KB
subtask2_04.txt AC 51 ms 5148 KB
subtask2_05.txt AC 32 ms 900 KB
subtask2_06.txt AC 51 ms 5144 KB
subtask2_07.txt AC 51 ms 5144 KB
subtask2_08.txt AC 49 ms 5144 KB
subtask2_09.txt AC 57 ms 5144 KB
subtask2_10.txt AC 57 ms 5144 KB
subtask2_11.txt AC 57 ms 5144 KB
subtask2_12.txt AC 58 ms 5144 KB
subtask2_13.txt AC 55 ms 5144 KB
subtask2_14.txt AC 49 ms 5144 KB
subtask2_15.txt AC 56 ms 5144 KB
subtask2_16.txt AC 50 ms 5144 KB
subtask2_17.txt AC 50 ms 5144 KB
subtask2_18.txt AC 50 ms 5144 KB
subtask2_19.txt AC 57 ms 5144 KB
subtask2_20.txt AC 58 ms 5144 KB
subtask2_21.txt AC 53 ms 4796 KB
subtask2_22.txt AC 57 ms 5144 KB
subtask2_23.txt AC 57 ms 5144 KB
subtask2_24.txt AC 49 ms 4324 KB
subtask2_25.txt AC 51 ms 4560 KB
subtask2_26.txt AC 55 ms 4916 KB
subtask2_27.txt AC 48 ms 4216 KB
subtask2_28.txt AC 28 ms 2816 KB
subtask2_29.txt AC 46 ms 4096 KB