Cod sursa(job #2589643)

Utilizator isa_tudor_andreiAndrei Tudor isa_tudor_andrei Data 26 martie 2020 17:48:27
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 30000;

int aib[1 + NMAX + 1], n;

void update( int p, int val ) {
  for( p; p <= n; p += p & (-p) )
    aib[p] += val;
}

int cb( int x ) {
  int pas;
  for( pas = 1; pas <= n; pas *= 2 );
  int r = 0;
  while( pas ) {
    if( r + pas <= n && aib[r + pas] < x ) {
      x -= aib[r + pas];
      r += pas;
    }
    pas /= 2;
  }
  return r + 1;
}

int main() {
    fin>>n;
    for( int i = 1; i <= n; i ++ ) {
      update(i, 1);
    }
    int sz = n;
    int tosearch = 1;
    for( int i = 1; i <= n; i ++ ) {
      tosearch += i;
      tosearch %= sz;
      int poz;
      if( tosearch == 0 )
        tosearch = sz;
      poz = cb(tosearch);
      update(poz, -1);
      fout<<poz<<" ";
      sz --;
      tosearch --;
    }
    return 0;
}