Cod sursa(job #2163212)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 12 martie 2018 17:14:25
Problema Order Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in ("order.in");
ofstream out ("order.out");
int const nmax = 30000;
int arb[5 + 3 * nmax];

#define MAX(a , b) ((a < b) ? b : a)
#define MIN(a , b) ((a < b) ? a : b)

int n;
void build(int node , int from , int to){
  arb[node] = (to - from + 1);
  if(from < to){
    int mid = (from + to) / 2;
    build(node * 2 , from , mid);
    build(node * 2 + 1 , mid + 1 , to);
  }
}
void update(int node , int from , int to ,int x , int val){
  if(from == to){
    arb[node] = val;
  } else{
    int mid = (from + to) / 2;
    if(x <= mid)
      update(node * 2 , from , mid , x , val);
    else
      update(node * 2 + 1 , mid + 1 , to , x , val);
    arb[node] = arb[node * 2] + arb[node * 2 + 1];
  }
}
int query(int node , int from , int to , int x , int y){
  if(from == x && to == y)
    return arb[node];
  else{
    int mid = (from + to) / 2;
    int result = 0;
    if(x <= mid)
      result += query(node * 2 , from , mid , x , MIN(y , mid));
    if(mid + 1 <= y)
      result += query(node * 2 + 1 , mid + 1 , to , MAX(x , mid + 1) , y);
    return result;
  }
}
int test(int start , int number){
  int lim = MIN(n , start + number);
  int result = query(1 , 1 , n , start + 1 , lim);
  number -= lim - start;
  result += number / n * query(1 , 1 , n , 1 , n);
  number %= n;
  if(0 < number)
    result += query(1 , 1 , n , 1, number);
  return result;
}
int binarysearch(int from , int to ,int start , int val){
  if(from < to){
    int mid = (from + to) / 2;
    if(test(start , mid) < val)
      return binarysearch(mid + 1 , to ,start ,  val);
    else
      return binarysearch(from , mid ,start ,  val);
  } else
    return from;
}
int main()
{
  in >> n;
  build(1 , 1 , n);
  int node = 1;
  for(int i = 1 ; i <= n ;i++){
    int pos = (node + binarysearch(1 , n * n , node , i) - 1) % n + 1;
    update(1 , 1 , n , pos , 0);
    node = pos;
    out<<node<<" ";
  }
  return 0;
}