Cod sursa(job #3350223)

Utilizator eric_dragosDragos Eric eric_dragos Data 6 aprilie 2026 14:40:40
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int n;
void update(vector<int> &aib, int i, int v){
    while(i <= n){
        aib[i] += v;
        i += i&(-i);
    }
}
int query(vector<int> &aib, int i){
    int s = 0;
    while(i > 0){
        s += aib[i];
        i -= i&(-i);
    }
    return s;
}
int kth(vector<int> &aib, int k){
    int l = 1, r = n;
    int ans = -1;
    while(l <= r){
        int mid = l+(r-l)/2;
        int tilmid = query(aib, mid);
        if(tilmid > k){
            r = mid-1;
        }
        else if(tilmid < k){
            l = mid+1;
        }
        else{
            ans = mid;
            r = mid-1;
        }
    }
    return ans;
}
void generateAIB(vector<int> &aib, vector<int> &v){
    for(int i = 1; i<=n; i++){
        update(aib, i, v[i]);
    }
}
int main(){
    fin >> n;
    vector<int> v(n+1, 1);
    vector<int> aib(n+1, 0);
    int poz = 1;
    generateAIB(aib, v);
    for(int i = 1; i<=n; i++){
        int remaining = n-i+1;
        int rang_poz = query(aib, poz);
        int rang_tinta = (rang_poz + i)%remaining;
        if(rang_tinta == 0) rang_tinta = remaining;
        poz = kth(aib, rang_tinta);
        update(aib, poz, -1);
        fout << poz << ' ';
    }

    return 0;
}