Cod sursa(job #2924203)

Utilizator CReaper1116Shang Cheng Lin CReaper1116 Data 26 septembrie 2022 23:26:14
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>

using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int fen[30000],n;
void add(int nr,int pos){
    for(int i = pos;i < n;i|=(i + 1)){
        fen[i]+=nr;
    }
}
int get(int pos){
    int r = 0;
    for(int i = pos;i >= 0;i&=(i + 1),i--){
        r+=fen[i];
    }
    return r;
}
int range(int l,int r){
    return get(r) - get(l - 1);
}
int bs(int l,int r,int pos,int moves){
    if(l == r)return l;
    int mij = (l + r)/2;
    int nr;
    if(pos + mij < n){
        nr = range(pos,pos + mij);
    }else{
        nr = range(pos,n - 1) + range(0,pos + mij - n);
    }
    if(nr >= moves)return bs(l,mij,pos,moves);
    else return bs(mij + 1,r,pos,moves);
}
int main()
{
    int cnt = 0,i,cur = 0;
    fin>>n;
    for(i = 0;i < n;i++){
        add(1,i);
    }
    for(i = 0;i < n;i++){
        int moves = (i + 1)%(n - i);
        if(moves == 0)moves = n - i;
        ///range (i,n - 1] + [1,i - 1)
        int nr = bs(0,n,(cur + 1)%n,moves);
        cur+=(nr + 1);
        cur%=n;
        fout<<cur%n + 1<<' ';
        add(-1,cur);
    }
    return 0;
}