Cod sursa(job #3248648)

Utilizator Iustin_Mircea2010Iustin Mircea Iustin_Mircea2010 Data 12 octombrie 2024 14:01:53
Problema Order Scor 100
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;
int n;
int aib[30005];
void update(int i, int val){
    while(i <= n){
        aib[i] += val;
        i += i&-i;
    }
}
int query(int i){
    int ret = 0;
    while(i){
        ret += aib[i];
        i -= i&-i;
    }
    return ret;
}
int cb(int poz){
    int ret = n;
    int st = 1, dr = n;
    while(st <= dr){
        int mij = (st+dr)/2;
        if(query(mij) <= poz){
            ret = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    return ret;
}
int adjust(int val, int poz){
    while(query(val) == poz)
        val--;
    return val + 1;
}
int main()
{
    ifstream cin("order.in");
    ofstream cout("order.out");
    cin >> n;
    for(int i = 1; i <= n; i++)
        update(i, 1);
    int poz = 2;
    for(int i = 1; i <= n; i++){
        poz = (poz + i - 1) % (n - i + 1);
        if(!poz)
            poz =  n - i + 1;
        int ans = cb(poz);
        ans = adjust(ans, poz);
        update(ans, -1);
        cout << ans << " ";
    }
    return 0;
}