Cod sursa(job #2831559)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 11 ianuarie 2022 18:00:04
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <stdio.h>

using namespace std;
const int NMAX = 30000;

int aib[NMAX + 1];

void update(int pos, int n, int val);

int main()
{
    int n, x, r;
    FILE *fin = fopen("order.in", "r");
    fscanf(fin, "%d", &n);
    fclose(fin);

    for (int i = 1; i <= n; i++)
        update(i, n, 1);

    FILE *fout = fopen("order.out", "w");
    x = 1, r = n;
    for (int i = 1; i <= n; i++) {
        x = ((x + i - 1) % r) + 1;
        int step = (1 << 14), pos = 0, sum = 0;
        while (step){
            if (pos + step <= n && sum + aib[pos + step] < x) {
                sum += aib[pos + step];
                pos +=step;
            }
            step >>= 1;
        }
        r--;
        x--;
        update(pos + 1, n, -1);
        fprintf(fout, "%d ", pos + 1);
    }
    fclose(fout);
    return 0;
}


void update(int pos, int n, int val) {
    for (; pos <= n; pos += (pos & -pos))
        aib[pos] += val;
}