Cod sursa(job #2699031)

Utilizator euyoTukanul euyo Data 23 ianuarie 2021 14:53:30
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#define left( a ) (a << 1)
#define right( a ) ((a << 1) + 1)
 
using namespace std;
 
ifstream fin( "order.in" );
ofstream fout( "order.out" );
 
const int MaxN = 30002;

int sum[4 * MaxN];
 
void build( int node, int l, int r ) {
  int mid = (l + r) / 2;
 
  sum[node] = r - l + 1;
  if ( l == r ) {
	return;
  }
  build( left( node ), l, mid );
  build( right( node ), mid + 1, r );
}
int del( int node, int l, int r, int x ) {
  int mid = (l + r) / 2, q;
  
  if ( l == r ) {
	sum[node] = 0;
	return l;
  }
  if ( sum[left( node )] >= x ) {
	q = del( left( node ), l, mid, x );
  } else {
    q = del( right( node ), mid + 1, r, x - sum[left( node )] );
  }
  sum[node] = sum[left( node )] + sum[right( node )];
  return q;
}
 
int main() {
  int n, pos;
  
  fin >> n;
  build( 1, 1, n );
  pos = 1;
  for ( int i = 1; i <= n; ++i ) {
    pos = (pos + i - 1) % (n - i + 1);
    fout << del( 1, 1, n, pos + 1 ) << " ";
  }  
  fin.close();
  fout.close();
  return 0;
}