Cod sursa(job #2756708)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 2 iunie 2021 16:25:22
Problema Order Scor 65
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.83 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 tree[4 * NMAX + 1];

void buildArbore(int node, int left, int right){
    tree[node] = right - left + 1;

    if(left == right){
        return;
    }

    int mid = left + (right - left) / 2;

    buildArbore(node * 2, left, mid);
    buildArbore(node * 2 + 1, mid + 1, right);
}

void sterg(int node, int left, int right){
    if(left == right){
        tree[node] = 0;
        return;
    }

    int mid = left + (right - left) / 2;

    if(pozSterg <= mid){
        sterg(node * 2, left, mid);
    }
    else {
        sterg(node * 2 + 1, mid + 1, right);
    }

    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int query(int node, int left, int right){
    if(A <= left && right <= B){
        return tree[node];
    }

    int mid = left + (right - left) / 2;

    int rez1 = 0, rez2 = 0;
    if(A <= mid){
        rez1 = query(node * 2, left, mid);
    }
    if(B >= mid + 1){
        rez2 = query(node * 2 + 1, mid + 1, right);
    }

    return rez1 + rez2;
}


int newPos(int pos, int q){
    q = (q - 1) % tree[1] + 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(1, 1, N) >= 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(1, 1, N);

            A = 1;
            B = mid;
            rez = rez + query(1, 1, N);

            //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;

    buildArbore(1, 1, N);

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

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

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

    return 0;
}