Cod sursa(job #2751431)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 14 mai 2021 23:30:48
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <bits/stdc++.h>

using namespace std;

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

struct SegTree {
  int Size;
  vector<int> tree;

  SegTree(int N) {
    Size = 1;
    while (Size < N)
      Size <<= 1;
    tree.resize(Size << 1);
  }

  int lSon(int x) {
    return x << 1;
  }

  int rSon(int x) {
    return x << 1 | 1;
  }

  void build(int x, int lx, int rx) {
    if (lx == rx) {
      tree[x] = 1;
      return;
    }
    int mid = (lx + rx) >> 1;
    build(lSon(x), lx, mid);
    build(rSon(x), mid + 1, rx);
    tree[x] = tree[lSon(x)] + tree[rSon(x)];
  }

  void update(int x, int lx, int rx, int poz) {
    if (lx == rx) {
      tree[x] = 0;
      return;
    }
    int mid = (lx + rx) >> 1;
    if (poz <= mid)
      update(lSon(x), lx, mid, poz);
    else update(rSon(x), mid + 1, rx, poz);
    tree[x] = tree[lSon(x)] + tree[rSon(x)];
  }

  int kth_one(int x, int lx, int rx, int k) {
    if (lx == rx)
      return lx;
    int mid = (lx + rx) >> 1;
    if (k <= tree[lSon(x)])
      return kth_one(lSon(x), lx, mid, k);
    return kth_one(rSon(x), mid + 1, rx, k - tree[lSon(x)]);
  }

  int sum(int x, int lx, int rx, int poz) {
    if (rx <= poz)
      return tree[x];
    int mid = (lx + rx) >> 1;
    int ans = sum(lSon(x), lx, mid, poz);
    if (mid < poz)
      ans += sum(rSon(x), mid + 1, rx, poz);
    return ans;
  }
};

void test_case() {
  int N;
  fin >> N;
  SegTree tree(N);
  tree.build(1, 1, N);
  int M = N, k = 1;
  for (int i = 1; i <= N; ++i) {
    k += i;
    k = (k - 1) % M + 1;
    int poz = tree.kth_one(1, 1, N, k);
    fout << poz << ' ';
    tree.update(1, 1, N, poz);
    if (poz > 1)
      k = tree.sum(1, 1, N, poz - 1);
    else k = 0;
    --M;
  }
}

void solve() {
  int T = 1;
  for (int tc = 0; tc < T; ++tc)
    test_case();
}

void close_files() {
  fin.close();
  fout.close();
}

int main() {
  solve();
  close_files();
  return 0;
}