Cod sursa(job #3265547)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 31 decembrie 2024 12:45:58
Problema Order Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
using namespace std;

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

int n,aint[120001];
void update(int nod,int st,int dr,int poz,int val){
    if(st==dr){
        aint[nod]+=val;
        return ;
    }
    int mij=(st+dr)/2;
    if(mij<poz) update(2*nod+1,mij+1,dr,poz,val);
    else update(2*nod,st,mij,poz,val);
    aint[nod]=aint[2*nod]+aint[2*nod+1];
}
int query(int nod,int st,int dr,int a,int b){
    if(a>dr || st>b) return 0;
    if(a<=st && dr<=b) return aint[nod];
    int mij=(st+dr)/2;
    return query(2*nod,st,mij,a,b)+query(2*nod+1,mij+1,dr,a,b);
}
int cautbin(int a){
    int st=1,dr=n,rasp=0;
    while(st<=dr){
        int mij=(st+dr)/2;
        if(query(1,1,n,1,mij)>=a){
            rasp=mij;dr=mij-1;
        }else st=mij+1;
    }
    return rasp;
}
int main()
{
    int a,i,cn,aux,j;
    cin>>n;cn=n;
    for(i=1;i<=n;i++)
        update(1,1,n,i,1);
    a=2;
    for(i=1;i<=n;i++){
        aux=cautbin(a);
        update(1,1,n,aux,-1);
        cout<<""<<aux<<" ";
        cn--;a+=i;
        if(cn) a=(a-1)%cn+1;
    }
    return 0;
}