Cod sursa(job #418524)

Utilizator mgntMarius B mgnt Data 15 martie 2010 23:02:31
Problema Farfurii Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <fstream>
using namespace std;

typedef long long int lli;
int const maxn = 100 * 1000;
struct node { int v; node * n; };

lli C[1+maxn];
node P[1+maxn];

int
main ( )
{
  lli N, K, i, m, r;
  node * x, * y, * z, * w;
  ifstream is("farfurii.in");
  ofstream os("farfurii.out");
  is >> N >> K;

  C[1]=0;
  for ( i=2; N>=i; ++i )
    { C[i]=C[i-1]+(i-1); }

  for ( i=0; N>i; ++i )
    { P[i].v=i; P[i].n=&P[1+i]; }

  P[N].v=N; P[N].n=0;

  m=N; r=K; x=&P[0];

  while ( 0<r )
  {
    y=x; i=1;
    while ( r <= C[m-i] )
      { ++i; y=y->n; }

    
    m-=i; i=1; z=y->n;
    while ( C[m]+i<r )
      { ++ i; z=z->n; }

    r-=i;

    w=z->n;
    z->n=w->n;
    w->n=y->n;
    y->n=w;
    x=w;
  }

  x=&P[0]; x=x->n;
  os << x->v;
  for ( i=2; N>=i; ++i )
    { x=x->n; os << ' ' << x->v; }

  os << endl;
  return 0;
}