Mai intai trebuie sa te autentifici.

Cod sursa(job #1775170)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 9 octombrie 2016 22:57:20
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#define lim 300005
int aib[lim],n;
int zeros(int x){return (x&(x-1))^x;}
void update(int poz,int val){
    while(poz<=n){
        aib[poz]+=val;
        poz+=zeros(poz);
    }
}
int query(int poz){
    int s=0;
    while(poz!=0){
        s+=aib[poz];
        poz-=zeros(poz);
    }
    return s;
}
int cautbin(int val){
    int i=0,pas=1<<18;
    while(pas!=0){
        if(i+pas<=n&&query(i+pas)<=val)
            i+=pas;
        pas/=2;
    }
    while(query(i)==val)
        i--;
    return i+1;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("order.in","r");
    fout=fopen("order.out","w");
    int i,val,elim;
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++)
        update(i,1);
    val=1;
    for(i=1;i<=n;i++){
        val=(val+i)%(n-i+1);
        if(val==0)
            val=n-i+1;
        elim=cautbin(val);
        fprintf(fout,"%d ",elim);
        update(elim,-1);
        val--;
    }
    fclose(fin);
    fclose(fout);
    return 0;
}