Cod sursa(job #2908741)

Utilizator Mendea_IanisMendea Ianis Teodor Mendea_Ianis Data 5 iunie 2022 15:24:12
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,A[120005],nr,caut,cnt,last,p;

void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        A[nod] = 1;
        return;
    }

    int mid = (st+dr)/2;

    build(2*nod, st, mid);
    build(2*nod+1, mid+1, dr);

    A[nod] = A[2*nod] + A[2*nod+1];
}
void update(int nod, int st, int dr, int poz)
{
    if(st == dr)
        {
            A[nod] = 0;
            return;
        }

    int mid = (st+dr)/2;

    if(mid<poz)
        update(2*nod+1,mid+1,dr,poz);
    else{
        update(2*nod,st,mid,poz);
    }

    A[nod] = A[2*nod] + A[2*nod+1];
}

int query(int nod, int st, int dr, int a, int b)
{
    if(a<=st && dr<=b)
    {
        return A[nod];
    }

    int mid = (st+dr)/2;

    int sol = 0;

    if(a<=mid)
    {
        sol += query(2*nod,st,mid,a,b);
    }
    if(mid<b)
    {
        sol += query(2*nod+1,mid+1,dr,a,b);
    }

    return sol;
}

int query2(int nod, int st, int dr, int poz)
{
    if(st == dr)
        return st;

    int mid = (st+dr)/2;

    if(A[2*nod]>=poz)
        return query2(2*nod,st,mid,poz);
    else{
        return query2(2*nod+1,mid+1,dr,poz - A[2*nod]);
    }

}

int main()
{
    fin>>n;
    build(1,1,n);
    last = 1;
    while(nr<n)
    {
        cnt = ((nr+1)%(n-nr));
        if(cnt == 0)
            cnt = n-nr;
        //ne aflam la pasul cnt
        p = query(1,1,n,last+1,n);
        if(cnt<=p)
        {
            //vom cauta pe arborele de interval pozitia copilului eliminat
            caut = query2(1,1,n,query(1,1,n,1,last) + cnt);
            fout<<caut<<' ';
            update(1,1,n,caut);
        }
        else{
            caut = query2(1,1,n,(cnt - p));
            fout<<caut<<' ';
            update(1,1,n,caut);
        }
        nr++;
        last = caut;
    }

}