Cod sursa(job #3261653)

Utilizator nokih53838Noki H nokih53838 Data 7 decembrie 2024 10:26:41
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
using namespace std;

string const task("order");
ifstream fin(task + ".in");
ofstream fout(task + ".out");

int const N(30005);
int n, aib[N], ramas;

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

inline int Query(int pos) {
    int q = 0;
    for (int i = pos; i >= 1; i -= i & -i)
        q += aib[i];
    return q;
}

inline int Next(int pos, int add) {
    add %= ramas;
    int queryPos = Query(pos);
    int capat = Query(n) - queryPos;
    if (capat >= add) {
        int st = pos + 1, dr = n, res = -1;
        while (st <= dr) {
            int mid = (st + dr) / 2;
            if (Query(mid) - queryPos >= add)
                res = mid, dr = mid - 1;
            else st = mid + 1;
        }
        return res;
    }
    else {
        int st = 1, dr = pos - 1, res = -1;
        while (st <= dr) {
            int mid = (st + dr) / 2;
            if (Query(mid) + capat >= add) 
                res = mid, dr = mid - 1;
            else st = mid + 1;
        }
        return res;
    }
}

int main() {

    fin >> n;
    for (int i = 1; i <= n; ++i)
        Update(i, 1);
    ramas = n;

    int pos = 1;
    for (int i = 1; i <= n; ++i) {
        pos = Next(pos, i);
        --ramas;
        Update(pos, -1);
        fout << pos << ' ';
    }

    fin.close();
    fout.close();
    return 0;
}