Cod sursa(job #829953)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 6 decembrie 2012 08:30:59
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#define NM 30010
#define Left 2*(Node)
#define Right 2*(Node)+1

using namespace std;

ifstream f("order.in");
ofstream g("order.out");

int N;
int i,j;
int sol,tot;
int lpoz;
int K,V,P;
int AI[4*NM];

void Update (int Node, int S, int D)
{
  if (S>=D)
  {
    AI[Node]+=V;
    return;
  }

  int M=(S+D)/2;

  if (P<=M)
    Update(Left,S,M);
  else
    Update(Right,M+1,D);

  AI[Node]=AI[Left]+AI[Right];
}

void Query (int Node, int S, int D)
{
  if (S>=D)
  {
    P=S;
    return;
  }

  int M=(S+D)/2;

  if (K<=AI[Left])
    Query(Left,S,M);
  else
  {
    K-=AI[Left];
    Query(Right,M+1,D);
  }
}

int QueryS (int Node, int S, int D)
{
  if (1<=S && D<=lpoz)
  {
    return AI[Node];
  }

  int M=(S+D)/2;
  int ANS=QueryS(Left,S,M);
  if (lpoz>M)
    ANS+=QueryS(Right,M+1,D);

  return ANS;
}

int main ()
{
  f >> N;

  for (i=1; i<=N; i++)
  {
    V=1;
    P=i;
    Update(1,1,N);
  }

  lpoz=1;
  for (i=1; i<=N; i++)
  {
    P=QueryS(1,1,N);
    tot=AI[1];
    K=(P+i-1)%tot+1;
    P=0;

    Query(1,1,N);
    V=-1;
    Update(1,1,N);

    g << P << ' ';
    lpoz=P;
  }

  g << '\n';

  f.close();
  g.close();

  return 0;
}