Cod sursa(job #1774312)

Utilizator Vlad_317Vlad Panait Vlad_317 Data 8 octombrie 2016 19:54:45
Problema Asmax Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
#include <cstring>
using namespace std;

const int MAX = 500000;

int a[MAX + 1];
bool f[2 * MAX];

int main()
{
    FILE *fin, *fout;

    fin = fopen("string.in", "r");
    fout = fopen("string.out", "w");

    int n;

    fscanf(fin, "%d\n", &n);

    for(int i = 1; i <= n; i++)
    {
        char c;
        fscanf(fin, "%c", &c);
        a[i] = c - 'a';
    }

    for(int l = 1; (1 << (l - 1)) <= n; l++)
    {
        memset(f, 0, sizeof(f));
        int x = 0;
        for(int i = 1; i <= l; i++)
            x = (x << 1) + a[i];
        for(int i = l + 1; i <= n; i++)
        {
            f[x] = 1;
            x = x - a[i - l] * (1 << (l - 1));
            x = (x << 1) + a[i];
        }
        f[x] = 1;
        for(int i = 0; i < (1 << l); i++)
            if(f[i] != 1)
            {
                fprintf(fout, "%d\n", l);
                for(int j = l - 1; j >= 0; j--)
                    if(i & (1 << j))
                        fprintf(fout, "b");
                    else
                        fprintf(fout, "a");
                return 0;
            }
    }

    return 0;
}