Cod sursa(job #2342729)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 13 februarie 2019 12:13:53
Problema Order Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

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

struct Treap;
Treap* NIL;

typedef pair<Treap*,Treap*> Trip;

struct Treap
{
  int k, p, size;
  Treap *st, *dr;

  Treap( int val, int pr=rand() )
  {
    k=val;
    p=pr;
    size=1;

    st=NIL, dr=NIL;
  }

  void resize( )
  {
    size=st->size+dr->size+1;
  }
};

Treap* join( Treap* a, Treap* b )
{
  if( a==NIL )
    return b;

  if( b==NIL )
    return a;

  if( a->p>b->p )
  {
    a->dr=join(a->dr,b);
    a->resize();

    return a;
  }
  else
  {
    b->st=join(a,b->st);
    b->resize();

    return b;
  }
}

Trip split( Treap* x, int pos )
{
  if( x==NIL )
    return Trip{NIL,NIL};

  if( pos<=x->st->size )
  {
    Trip t=split(x->st,pos);

    x->st=t.second;
    x->resize();

    return Trip{t.first,x};
  }
  else
  {
    Trip t=split(x->dr,pos-x->st->size-1);

    x->dr=t.first;
    x->resize();

    return Trip{x,t.second};
  }
}

int access( Treap* x, int pos )
{
  if( pos<=x->st->size )
    return access(x->st,pos);

  if( pos>x->st->size+1 )
    return access(x->dr,pos-x->st->size-1);

  return x->k;
}

void displayTreap(Treap *root, int space = 0) {
  for(int i = 0; i < space; ++i)
    fout<<" ";

  fout<<"INFO: "<<root->k<<" "<<root->p<<"{\n";

  if( root->st!=NIL )
    displayTreap(root->st,space+2);

  if( root->dr!=NIL )
    displayTreap(root->dr,space+2);

  for(int i = 0; i < space; ++i)
    fout << " ";
  fout<<"}\n";
}

int main()
{
  int n;

  fin>>n;

  NIL=new Treap(-1);
  NIL->p=-1;
  NIL->size=0;
  NIL->st=NIL->dr=NIL;

  Treap* root=NIL;

  for( int i=1;i<=n;i++ )
    root=join(root,new Treap(i,i));

  int poz=1;

  for( int i=1;i<n;i++ )
  {
    poz=(poz+i-1)%(n-i+1)+1;

    fout<<access(root,poz)<<" ";

    Trip t1=split(root,poz-1);
    Trip t2=split(t1.second,1);

    root=join(t1.first,t2.second);

    poz--;
  }

  fout<<access(root,1);

  return 0;
}