Cod sursa(job #1946212)

Utilizator RaZxKiDDavid Razvan RaZxKiD Data 29 martie 2017 23:07:26
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>

#define zeros(x) ((-x)&(x))

using namespace std;

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

int n,AIB[30005];
void add(int x, int val){
    for(int i=x;i<=n;i+=zeros(i)){
        AIB[i]+=val;
    }
}
int sum(int x){
    int s=0;
    for(int i=x;i>=1;i-=zeros(i)){
        s+=AIB[i];
    }
    return s;
}

void read(){
    in>>n;
}
void solve(){
    for(int i=1;i<=n;i++){
        add(i,1);
    }
    int pos=2;
    out<<"2 ";
    add(2,-1);
    for(int i=1;i<n;i++){
        pos+=i;
        pos%=(n-i);
        if(pos==0)
            pos=n-i;
        int st=1,dr=n,sol=1,mij;
        while(st<=dr){
            mij=(st+dr)/2;
            if(sum(mij)>=pos){
                sol=mij;
                dr=mij-1;
            }
            else st=mij+1;
        }
        add(sol,-1);
        out<<sol<<" ";
    }
}
int main(){
    read();
    solve();
    return 0;
}