Cod sursa(job #3245251)

Utilizator angelaAngela Visuian angela Data 28 septembrie 2024 08:24:50
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
using namespace std;
	
ifstream fin("order.in");	
ofstream fout("order.out");
	
const int NMAX = 30005;
int st[4 * NMAX], n;
int nr = 1;  // st[x] => suma val de 1 pe interval (nr copii existenti)
	
void Build(int x, int l, int r)
{
	if (l == r)
	{
        st[x] = 1;
        return;
    }
	
    int m = (l + r) / 2;
	
    Build(2 * x, l, m);
    Build(2 * x + 1, m + 1, r);
    st[x] = st[2 * x] + st[2 * x + 1];
}
	
void Update(int x, int l, int r, int nr)
{	
    if (l == r)
    {
        fout << l << " ";   // gasim copilul
        st[x] = 0;        // il stergem 
        return;
    }
	
    int m = (l + r) / 2;
	
    if (nr <= st[2 * x])	
        Update(2 * x, l, m, nr);
    else	
        Update(2 * x + 1, m + 1, r, nr - st[2 * x]);
	
    st[x] = st[2 * x] + st[2 * x + 1];
}
	
int main()
{
    fin >> n;
	
    Build(1, 1, n);
	
    for (int i = 1 ; i <= n ; i++)
    {
		// la cati mai erau adaug cati trebuie sa mai fie la pasul curent
		nr += i;            // nr copii care trebuie sa mai existe incepand de la poz 1 (pe ultimul il sterg)
        if (nr <= st[1])   // daca mai sunt suficienti copii pe cerc  (st[1] = nr total existenti pe cerc)
        {
			              
			Update(1, 1, n, nr);  // sterg 1
			nr--;                 
        }
        else
        {
            nr = (nr - 1) % st[1] + 1; // cati trebuie sa mai existe incepand de la poz 1
	        Update(1, 1, n, nr);
			nr--;
		}
	}
  
    return 0;
}