Cod sursa(job #2384825)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 21 martie 2019 10:54:54
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 30005;
const int INF = 2000000000;

int N;
int tree[NMAX];

vector <int> sol;

void Read()
{
  fin >> N;

  fin.close();
}

int Query( int pos )
{
  int sum = 0;

  while( pos > 0 )
  {
    sum += tree[pos];
    pos -= pos & -pos;
  }

  return sum;
}

void Update( int pos, int val )
{
  while( pos <= N )
  {
    tree[pos] += val;
    pos += pos & -pos;
  }
}

int BinSearch( int lf, int rg, int val )
{
  if( lf > rg ) return INF;

  int mid = ( lf + rg ) / 2;
  int q = Query( mid );

  //fout << mid << ' ' << q << '\n';

  if( q == val ) return min( mid, BinSearch( lf, mid - 1, val ) );

  if( q > val ) return BinSearch( lf, mid - 1, val );
  else return BinSearch( mid + 1, rg, val );
}

void Do()
{
  int curent, target;
  int p;

  for( int i = 1; i <= N; ++i )
    Update( i, 1 );

  sol.push_back( 2 );
  Update( 2, -1 );

  curent = 2;

  for( int i = 2; i <= N; ++i )
  {
    int qN = Query( N ), qC = Query( curent );

    if( qN - qC >= i )
    {
      target = qC + i;

      p = BinSearch( curent + 1, N, target );

      sol.push_back( p );

      Update( p, -1 );

      curent = p;
    }
    else
    {
      target = ( qC + i ) % qN ;
      if( target == 0 ) target = qN;

      p = BinSearch( 1, N, target );

      sol.push_back( p );

      Update( p, -1 );

      curent = p;
    }
  }

  for( int i = 0; i < sol.size(); ++i )
    fout << sol[i] << ' ';
}

int main()
{
    Read();
    Do();

    return 0;
}