Cod sursa(job #2378774)

Utilizator aditzu7Adrian Capraru aditzu7 Data 12 martie 2019 16:54:10
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>

using namespace std;
int sol[30001],poz,i,n, aib[30001],v[30001];
void add(int x,int val){
int i;
for(i=x;i<=n;i+=(i&(-i))) aib[i]+=val;



}
int sum(int x){
int i,rasp=0;
for(i=x;i>=1;i-=(i&(-i))) rasp+=aib[i];
return rasp;

}
int cb(int val){
int mmin=n+1,st=1,dr=n,mij;
while(st<=dr){
    mij=(st+dr)>>1;
int ss=sum(mij);
if(ss==val&&mij<mmin) mmin=mij;
    else if(ss>=val) dr=mij-1;
    else st=mij+1;

}
return mmin;

}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++) add(i,1);
  //  for(i=1;i<=n;i++) scanf("%d",&v[i]);
    int nrc=n;
    int poz=2;
    for(i=1;i<=n;i++){
        nrc--;
        int val=cb(poz);
        sol[i]=val;
        poz+=i;
        add(val,-1);
        if(nrc)
            if(poz%nrc) poz%=nrc;
        else poz=nrc;



    }
    for(i=1;i<=n;i++) printf("%d ",sol[i]);

    return 0;
}