Cod sursa(job #3166063)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 7 noiembrie 2023 17:12:58
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const long long INF = 1000000000000000000;
const int mod = 1e9 + 7;
const char out[2][4]{ "NO", "YES" };
#define all(A) A.begin(), A.end()
using ll = long long;
ifstream fin("order.in");
ofstream fout("order.out");

#define variableName(var) #var
#define __debug(var) cout << #var << " = " << var << '\n'
inline int rint(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }


const int nmax = 30000;

int t[nmax + 5]{ 0 };

int n, lg = 0;

void build() {
    for (int i = 1; i <= n; ++i) {
        t[i]++;
        if (i + (i & -i) <= n) {
            t[i + (i & -i)] += t[i];
        }
    }
}

void add(int i, int x) {
    for (; i <= n; i += i & -i) {
        t[i] += x;
    }
}

int get(int i) {
    int sum = 0;
    for (; i > 0; i -= i & -i) {
        sum += t[i];
    }
    return sum;
}

int get(int i, int j) {
    return get(j) - get(i - 1);
}

int current = 1;

// assumming x is 1
/*
1 2 3 4 5 6
1 1 1 1 1 1
^
1 2 3 4 5 6
1 0 1 1 1 1
  ^
1 2 3 4 5 6
1 0 1 0 1 1
      ^

1 2 3 4 5 6
0 0 1 0 1 1
^

1 2 3 4 5 6
0 0 0 0 1 1
    ^

1 2 3 4 5 6
0 0 0 0 0 1
          ^

1 2 3 4 5
1 2 3 4 0
0 1 2 3 4


*/
int offset(int i, int x) {
    x = (x - 1) % get(n) + 1;
    int after = get(i + 1, n);
    if (after < x) {
        x -= after;
        i = 0;
    }
    int st = i + 1, dr = n, j = -1;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (get(i + 1, mid) >= x) {
            j = mid, dr = mid - 1;
        }
        else {
            st = mid + 1;
        }
    }
    return j;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    fin >> n;
    while ((1 << (lg + 1)) <= n) {
        lg++;
    }
    build();
    for (int i = 1; i <= n; ++i) {
        current = offset(current, i);
        fout << current << sp;
        add(current, -1);
    }
}