ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1706. Шифровка 2

Wrong answer 2... Please help (Code in here)
Послано georgi_georgiev 2 окт 2009 20:51
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string a;
int k;
int array[9096], n, bucket[9096], lbucket[9096], h = 0;
void scan(){
    cin >> k >> a;
    a += a.substr(0, k - 1);
    n = a.size();
}
bool f(int x, int y){
    if ( !h )
        return a[x] < a[y];
    if ( bucket[x] < bucket[y] ) return 1;
    if ( bucket[y] < bucket[x] ) return 0;
    int bx, by;
    if ( x + h >= n ) bx = n - (x + h) - 1;
    else bx = bucket[x + h];
    if ( y + h >= n ) by = n - (y + h) - 1;
    else by = bucket[y + h];
    return bx < by;
}
bool makebuckets(){
    int br = 0;
    for ( int i = 0; i < n; ++i ){
        if ( i > 0 )
            if ( f(array[i], array[i - 1]) || f(array[i - 1], array[i]) )
                ++br;
        lbucket[array[i]] = br;
    }
    for ( int i = 0; i < n; ++i )
        bucket[i] = lbucket[i];
    ++br;
    return (br == n);
}
void buildsuffixarray(){
    for ( int i = 0; i < n; ++i )
        array[i] = i;
    sort (array, array + n, f);
    if ( makebuckets() ) return;
    for ( h = 1;; h *= 2 ){
        sort(array, array + n, f);
        if ( makebuckets() ) break;
    }
}
int findnext(int st, int i){
    ++i;
    for (i; i < n; ++i)
        if ( array[i] >= st && array[i] < st + k ) return i;
    return -1;
}
int rez(int t){
    int p = findnext(t, -1), d, result = (k + 1) * k / 2;
    d = findnext(t, p);
    int br = 0;
    while ( d > 0 ){
        int j = 0;
        while ( a[array[p] + j] == a[array[d] + j] && array[p] + j < t + k && array[d] + j < t + k ) ++j;
        result -= j;
        p = d;
        d = findnext(t, d);
        ++br;
    }
    if ( br != k - 1 ) while(1);
    return result;
}
void solve(){
    buildsuffixarray();
    cout << rez(0);
    for ( int i = 1; i < n - k + 1; ++i )
        cout << " " << rez(i);
    cout << endl;
}
int main(){
    scan();
    solve();
}

I am getting mad... no idea where my code is wrong... The idea is right