Cod sursa(job #1997849)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 5 iulie 2017 16:13:25
Problema Order Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n;
int arbInt[400001];
int pozSiNrCaut;
int nrCopii;

void creeareArbore(int pozNod, int  st, int dr){
  if(st == dr){
    arbInt[pozNod] = 1;
    return ;
  }
  int mijloc = (st + dr) / 2 ;
  creeareArbore(pozNod * 2, st, mijloc);
  creeareArbore(pozNod * 2 + 1, mijloc + 1, dr);
  arbInt[pozNod] = arbInt[pozNod * 2] + arbInt[pozNod * 2 + 1];
}

void cautareElement(int pozNod , int st, int dr){
  if(st == dr){
    out << st << ' ';
    arbInt[pozNod] = 0;
    return ;
  }
  int mijloc = (st + dr) / 2;
  if(pozSiNrCaut <= arbInt[pozNod * 2])//am destule nr pe stanga
    cautareElement(pozNod * 2, st, mijloc);
  else {
    pozSiNrCaut = pozSiNrCaut - arbInt[pozNod * 2] ;//scad cate sunt pe stanga si caut a "pozSiNrCaut"-a poz din intervalul drept
    cautareElement(pozNod * 2 + 1, mijloc + 1, dr);
  }
  arbInt[pozNod] =  arbInt[pozNod * 2] + arbInt[pozNod * 2 + 1];//actualizare valori
}

void rezolvare(){
  in >> n;
  for(int i = 1; i <= n; i++)
    creeareArbore(1,1,n);
  pozSiNrCaut = 1;
  nrCopii = n;
  int aux = 1;
  for(int i = 1; i <= n; i++){//trebuie sa scot n copii
    aux = aux + i;
    if(i != 1)// la fiecare are loc o schimbare de semn
      aux --;
    if(aux > nrCopii)//depasesc limita
      aux %= nrCopii;
    if(aux == 0)
      aux = nrCopii;
    if(i == n)
      aux = 1;
    pozSiNrCaut = aux;
    cautareElement(1, 1, n);
    nrCopii = arbInt[1];
  }
}

int main(){
  rezolvare();
  return 0;
}