Cod sursa(job #2903030)

Utilizator AdelaCorbeanuAdela Corbeanu AdelaCorbeanu Data 17 mai 2022 01:19:09
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("order.in");
ofstream fout ("order.out");

const int N = 2e5 + 5;

bool f[N];
int a[N], tree[N * 4];

void update(int left, int right, int node, int pos) {
    if (left > right) {
        return ;
    }
    if (left == right) {
        tree[node] = 1;
        return ;
    }
    int mid = (left + right) >> 1;
    if (mid >= pos) {
        update(left, mid, node * 2, pos);
    }
    else {
        update(mid + 1, right, node * 2 + 1, pos);
    }
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int query(int left, int right, int node, int x, int y) {
    if (left > right) {
        return 0;
    }
    if (left >= x && right <= y) {
        return tree[node];
    }
    int mid = (left + right) >> 1;
    int ans1 = 0, ans2 = 0;
    if (mid >= x) {
        ans1 = query(left, mid, node * 2, x, y);
    }
    if (mid + 1 <= y) {
        ans2 = query(mid + 1, right, node * 2 + 1, x, y);
    }
    return ans1 + ans2;
}

int main()
{

    int n, k, sol = 1, cnt = 0, cntt = 1;
    int pos = 1;

    fin >> n;
    fout << "2" << " ";
    update(1, n, 1, 2);
    pos = 3;
    if (pos > n)
        pos = 1;
    do {
        ++cntt;
        k = cntt;
        int kk = k;
        if(kk >= n - sol) {
            kk %= (n - sol);
        }
        int left = 1, right = n - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            int nxt_pos = mid + pos - 1, ans = 0;
            if (nxt_pos <= n) {
                ans += mid - query(1, n, 1, pos, nxt_pos) + 1;
            }
            else {
                ans += mid - query(1, n, 1, 1, nxt_pos % n) - query(1, n, 1, pos, n) + 1;
            }
            if (ans >= kk + 1) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        pos += left - 1;
        if (pos > n) {
            pos -= n;
        }
        ++sol;
        fout << pos << " ";
        update(1, n, 1, pos);
        ++pos;
        if (pos > n)
            pos -= n;

    }
    while (sol < n);
    return 0;
}