Cod sursa(job #3251056)

Utilizator iuliacarpIulia Carp iuliacarp Data 24 octombrie 2024 18:15:14
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int n,lg,Aib[30002];
void update(int poz,int val){
    for(int i=poz;i<=n;i+=i&-i)
        Aib[i]=Aib[i]+val;
}
int query(int poz){
    int s=0;
    for(int i=poz;i>=1;i-=i&-i)
        s=s+Aib[i];
    return s;
}
int c_bin(int lg){
    int st=1,dr=n,pmin=0;
    while(st<=dr){
        int mij=(st+dr)/2;
        int nr=query(mij);
        if(nr>=lg) pmin=mij,dr=mij-1;
        else st=mij+1;
    }
    return pmin;
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        update(i,1);
    int nn=n;
    lg=2;
    for(int i=1;i<=n;i++){
        int poz=c_bin(lg);
        update(poz,-1);
        fout<<poz<<" ";
        nn--,lg=lg+i;
        if(nn) lg=lg%nn==0?nn:lg%nn;
    }
    return 0;
}