Cod sursa(job #2777110)

Utilizator pctirziuTirziu Petre pctirziu Data 22 septembrie 2021 09:57:27
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>

using namespace std;
ifstream cin("order.in");
ofstream cout("order.out");
int n;
int aib[30005];
void update(int x, int val)
{
    int i;
    for(i = x; i <= n; i += (i & -i))
        aib[i] += val;
}
int solve(int x)
{
    int i, sum = 0;
    for(i = x; i >= 1; i -= (i & -i))
        sum += aib[i];
    return sum;
}
int main()
{
    int i;
    cin >> n;
    for(i = 1; i <= n; i++)
        update(i, 1);
    int poz = 2;
    for(i = 1; i <= n; i++){
        poz = (poz + i - 1) % (n - i + 1);
        if(poz == 0)
            poz = n - i + 1;
        int st = 1, dr = n, med, ans;
        while(st <= dr){
            med = (st + dr) / 2;
            if(solve(med) <= poz){
                st = med + 1;
                ans = med;
            }
            else
                dr = med - 1;
        }
        while(solve(ans) == poz)
            ans--;
        ans++;
        cout << ans << " ";
        update(ans, -1);
    }
    return 0;
}