Cod sursa(job #2756711)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 2 iunie 2021 16:32:45
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <iostream>
#include <fstream>

#define NMAX 30000

using namespace std;

ifstream fin ("order.in");
ofstream fout ("order.out");

int N;
int pozSterg;
int A, B;
int aib[NMAX + 1];

void buildAIB(){
    for(int i = 1; i <= N; i++){
        aib[i] = i & (-i);
    }
}

void sterg(int poz){
    for(int i = poz; i <= N; i += i & (-i)){
        aib[i] -= 1;
    }
}

int query(int poz){
    int rez = 0;
    for(int i = poz; i >= 1; i -= i & (-i)){
        rez += aib[i];
    }

    return rez;
}


int newPos(int pos, int q){
    q = (q - 1) % query(N) + 1; //tree[1] adica cati am in [1, N]

    int lo = pos;
    int hi = N + 1;
    //de fapt caut in [pos + 1, N]

    while(hi - lo > 1){
        int mid = lo + (hi - lo) / 2;

        A = pos;
        B = mid;
        if( query(B) - query(A - 1) >= q){
            hi = mid;
        }
        else {
            lo = mid;
        }
    }

    //candidatul la raspuns ar trebui sa se afle in hi
    if(hi < N + 1){
        //inseamna ca exista in [pos + 1, N] solutie
        return hi;
    }
    else {
        //inseamna ca nu exista in [pos + 1, N] solutie
        //si caut pe [1, pos - 1]

        lo = 0;
        hi = pos;

        while(hi - lo > 1){
            int mid = lo + (hi - lo) / 2;

            int rez = 0;

            A = pos;
            B = N;
            rez = rez + query(B) - query(A - 1);

            A = 1;
            B = mid;
            rez = rez + query(B) - query(A - 1);

            //query(pos, N) + query(1, mid)

            if(rez >= q){
                hi = mid;
            }
            else {
                lo = mid;
            }
        }

        //acum raspunsul sigur se afla in hi
        return hi;
    }

}

int main()
{
    fin >> N;

    buildAIB();

    int pos = 1;
    for(int q = 1; q <= N; q++){
        //vreau sa gasesc acel Z ce reprezinta poz + q

        if(q != 1){
            sterg(pos);
        }

        pos = newPos(pos, q);
        //prima oara caut in [poz + 1, N]
        //dupa care in [1, poz - 1]
        fout << pos << ' ';
    }

    return 0;
}