fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. int tree_size;
  5. vector<int> tree;
  6. void tree_add(int idx, int delta) {
  7.     for (; idx <= tree_size; idx += idx & -idx) {
  8.         tree[idx] += delta;
  9.     }
  10. }
  11. int tree_query(int idx) {
  12.     int sum = 0;
  13.     for (; idx > 0; idx -= idx & -idx) {
  14.         sum += tree[idx];
  15.     }
  16.     return sum;
  17. }
  18. int find_kth_free(int k) {
  19.     int idx = 0;
  20.     for (int i = 1 << 16; i > 0; i >>= 1) {
  21.         if (idx + i <= tree_size && tree[idx + i] < k) {
  22.             idx += i;
  23.             k -= tree[idx];
  24.         }
  25.     }
  26.     return idx + 1;
  27. }
  28.  
  29. int main() {
  30.     ios_base::sync_with_stdio(false);
  31.     cin.tie(NULL);
  32.  
  33.     int n;
  34.     if (!(cin >> n)) return 0;
  35.     tree_size = n;
  36.     tree.assign(n + 1, 0);
  37.     vector<int> result(n + 1);
  38.     for (int i = 1; i <= n; i++) {
  39.         tree_add(i, 1);
  40.     }
  41.     int current_free_rank = 0;
  42.  
  43.     for (int i = 1; i <= n; i++) {
  44.         int free_slots_left = n - i + 1; 
  45.         current_free_rank = (current_free_rank + i) % free_slots_left;
  46.  
  47.         int target_rank = current_free_rank + 1;
  48.         int actual_pos = find_kth_free(target_rank);
  49.         result[actual_pos] = i;
  50.         tree_add(actual_pos, -1);
  51.         current_free_rank = target_rank - 1;
  52.     }
  53.     for (int i = 1; i <= n; i++) {
  54.         cout << result[i] << " ";
  55.     }
  56.     cout << "\n";
  57.  
  58.     return 0;
  59. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zBr2VB
language:
C++ (gcc 8.3)
created:
12 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!