Cod sursa(job #2917911)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 8 august 2022 16:57:26
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <bits/stdc++.h>
#define L D + 5
#define D (1 << 15)
#define lsb(x) (x & (-x))
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int aib[L];

inline void update(int pos, int val){
  for (; pos < L; pos += lsb(pos))
    aib[pos] += val;
}

inline int query(int x){
	int i, ret = 0, s = 0;
	for (i = D; i; i /= 2)
		if (aib[ret + i] + s < x){
			ret += i;
			s += aib[ret];
		}
	return ret;
}

int main(){
  int n, i, x = 2, y = 2;
  fin >> n;
  for (i = 1; i <= n; i++)
    update(i, 1);
  fout << "2 ";
  for (i = 1; i < n; i++){
    update(x, -1);
    y = (y + i - 1) % (n - i) + 1;
    x = query(y) + 1;
    fout << x << " ";
  }
  fout << "\n";
  return 0;
}