Cod sursa(job #2831563)

Utilizator DordeDorde Matei Dorde Data 11 ianuarie 2022 18:07:00
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<bits/stdc++.h>
#define z(x) ((x)&(-x))
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int const N = 30001;
int n;
class aib{
public:
    int v[N];
    aib(){
        fill(v , v + N , 0);
    }
    void add(int p , int x){
        for(int i = p ; i <= n ; i += z(i))
            v[i] += x;
    }
    int sum(int p){
        int r = 0;
        for(int i = p ; i ; i -= z(i))
            r += v[i];
        return r;
    }
}t;
int solve(int k){
    int pas = (1 << 15) , r = 0;
    while(pas){
        if(pas + r <= n && t.sum(pas + r) < k)
            r += pas;
        pas >>= 1;
    }
    return r + 1;
}
int main()
{
    fin >> n;
    for(int i = 1 ; i <= n ; ++ i)
        t.add(i , 1);
    int idx = 2 , tot = n;///incep de la primul nescos
    for(int i = 1 ; i <= n ; ++ i){
        ///il vreau pe start + i % ramase nescos
        idx = (idx + i - 2) % tot + 1;
        int x = solve(idx);
        t.add(x , -1);
        -- tot;
        fout << x << ' ';
    }
    return 0;
}