Cod sursa(job #2275219)

Utilizator 2016Teo@Balan 2016 Data 2 noiembrie 2018 21:59:26
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("order.in");
ofstream out("order.out");
#define max 30000
int bit[max],v[max];
int n;
int upt(int i,int add) {
    for(; i<=n; i+=(i&-i))
        bit[i]+=add;
}
int see(int i) {
    int ans=0;
    for(; i>0; i-=(i&-i))
        ans+=bit[i];
    return ans;
}
int bs(int k) {
    int l=0,h=n;
    while(l<h) {
        int mid =(l+h)/2;
        if (k<=see(mid))
            h=mid;
        else
            l=mid+1;
    }
    return l;
}
int main() {
    int i,ans,r=2;
    in>>n;
    for(i=1; i<=n; i++)
        upt(i,1);
    for(i=1; i<=n; i++) {
        ans=bs((r=(r+i-2)%(n+1-i)+1));
        upt(ans,-1);
        out<<ans<<' ';
    }
    return 0;
}