Cod sursa(job #3168479)

Utilizator emazareMazare Emanuel emazare Data 12 noiembrie 2023 15:29:52
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>

using namespace std;

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

const int Nmax = 30005;
int n,aib[4*Nmax];

void update(int x, int y){
    for(int i=x;i<=n;i+=(i&(-i)))
        aib[i]+=y;
}
int query0(int x){
    if(x == 0)
        return 0;
    int s = 0;
    for(int i=x;i>0;i-=(i&(-i)))
        s+=aib[i];
    return s;
}
int query(int x, int pas){
    if(x == 0)
        return 0;
    if(x>n){
        x = x%n;
        if(x == 0)
            x = n;
        return (query0(x)+n-pas+1);
    }
    return query0(x);
}

int main()
{
    int i,j,pos,st,dr,mid,sol = 0;
    fin >> n;
    for(i=1;i<=n;i++)
        update(i,1);
    pos = 1;
    for(i=1;i<=n;i++){ /// sa nu uiti sa faci ca n sa devina 0 la final;
        st = pos+1; dr = n+pos; j = i%(n-i+1);
        if(j == 0)
            j = n-i+1;
        while(st<=dr){
            mid = (st+dr)/2;
            int val = query(pos,i);
            if(query(mid,i)-val>=j){
                dr = mid-1;
                sol = mid;
            }
            else
                st = mid+1;
        }
        sol%=n;
        if(sol == 0)
            sol = n;
        fout << sol << " ";
        update(sol,-1);
        pos = sol%n;
    }
    return 0;
}