Submission #527701

#	Time	Username	Problem	Language	Result	Execution time	Memory
527701		vjudge1	Beads and wires (APIO14_beads)	C++14	0 / 100	1068 ms	1884 KiB

beads

#include<iostream>
#include<stdio.h>
#include<string.h>
#define mx 1000005
using namespace std;

char arr[mx];
int prefix[mx];

void prefix_array(string s)
{
    int l = s.length();

    for(int i=1; i<l; i++)
    {
        int j = prefix[i-1];

        while(j>0 && s[i]!=s[j])
        {
            j = prefix[j-1];
        }

        if(s[i]==s[j])
        {
            j++;
        }

        prefix[i] = j;
    }

}

int main()
{
    while(scanf("%s",arr))
    {
        int l= strlen(arr);
        if(arr[0]=='.')
            break;

        prefix_array(arr);
        int d = l - prefix[l-1];
        if(l%d==0)
        {
            cout << l/d << endl;
        }
        else
        {
            cout << 1 << endl;
        }
    }
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43