Cod sursa(job #3364594)

Utilizator TudorMitMituca Tudor TudorMit Data 6 septembrie 2026 19:05:11
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
using namespace std;

ifstream cin("order.in");
ofstream cout("order.out");

long long aib[30005];
int n;

void upd(int poz, int val){
    for(int i=poz;i<=n;i+=i&-i)
        aib[i]+=val;
}

int qr(int k){
    int poz=0;
    for(int i=1<<15;i>0;i>>=1){
        if(poz+i<=n && aib[poz+i]<k){
            poz+=i;
            k-=aib[poz];
        }
    }
    return poz+1;
}

int sum(int poz){
    int s=0;
    for(int i=poz;i>0;i-=i&-i)
        s+=aib[i];
    return s;
}

int main(){
    int poz=1,el,s;
    cin>>n;
    for(int i=1;i<=n;i++)
        upd(i,1);
    for(int i=1;i<=n;i++){
        s=sum(poz-1);
        el=(s+i)%(n-i+1);
        if(el==0)
            el=n-i+1;
        el=qr(el);
        cout<<el<<' ';
        upd(el,-1);
        if(i<n){
            poz=el+1;
            if(poz>n)
                poz=1;
            while(sum(poz)==sum(poz-1)){
                poz++;
                if(poz>n)
                    poz=1;
            }
        }
    }
    return 0;
}