Cod sursa(job #3320982)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 7 noiembrie 2025 20:08:31
Problema Order Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <bits/stdc++.h>
using namespace std;
//#define TESTS
#define FIO


#define x first
#define y second
#define pii pair<int,int>
#define veci vector<int>
#define vecp vector<pii>
#define all(x) x.begin(), x.end()
#define pb(x,y) x.push_back(y)

struct trnod{
	int size=1,val,h;
	trnod *l=NULL, *r=NULL;
	trnod(int val) {size=1, this->val=val, this->h=val; }
	~trnod() {delete l; delete r;}
};

struct treap{
	trnod *root=NULL;

	int nid(trnod *x)
	{
		return  1+nsize(x->l);
	}
	int nsize(trnod *x)
	{
		return x ? x->size : 0;
	}
	void nfix(trnod *x)
	{
		if(x) x->size = 1+ nsize(x->l) + nsize(x->r);
	}

	trnod* nmerge(trnod *l, trnod *r)
	{
		if((!l)||(!r)) return l?l:r;
		if(l->h < r->h)
		{
			l->r = nmerge(l->r, r);
			nfix(l);
			return l;
		}
		r->l= nmerge(l, r->l);
		nfix(r);
		return r;
	}

	void nsplit(trnod *t, trnod *&l, trnod *&r, int id, int add=0)
	{
		if(!t) {l=r=NULL; return;}
		//cerr<<"HERE "<<nid(t)<<' '<<add<<'\n';
		int my_id = nid(t)+add;
		if(my_id<=id)
		{
			l=t;
			nsplit(t->r, t->r, r, id, my_id);
			nfix(t);
			return;
		}

		r=t;
		nsplit(t->l, l, t->l, id, add);
		nfix(t);
		return;
	}

	void insert(int poz, int val)
	{
		trnod *t =new trnod(val);
		trnod *l, *r;
		//cerr<<"here\n";
		nsplit(root, l, r, poz);
		nprint(l);
		//cerr<<" : ";
		nprint(r);
		//cerr<<'\n';
		//cerr<<"here!\n";
		l=nmerge(l, t);
		root=nmerge(l,r);
	}

	void erase(int st, int dr)
	{
		trnod *l, *mid, *r;
		nsplit(root, l, r, dr);
		nsplit(l, l, mid, st-1);

		//cerr<<"WHAR "<<(mid?(mid->val):-1)<<'\n'; 

		delete mid;
		root=nmerge(l,r);
	}

	int get(int poz)
	{
		trnod *c=root;
		while(true)
		{
			//cerr<<"HEY "<<(c?c->val:-1)<<'\n';
			int id=nid(c);
			if(id==poz) return c->val;
			else if(id>poz) c=c->l;
			else poz-=id, c=c->r;
		}
	}

	void nprint(trnod*t)
	{
		if(!t) return;
		nprint(t->l);
		//cerr<<t->val<<','<<t->size<<' ';
		nprint(t->r);
	}

	void print()
	{
		nprint(root);
		//cerr<<'\n';
	}

	int size()
	{
		return nsize(root);
	}

	~treap() {delete root;}
};

void solve()
{
	treap tr;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		//cerr<<i<<' ';
		tr.insert(i,i);
		//cerr<<tr.size()<<'\n';
		tr.print();
	}

	//cerr<<"here\n";

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

		//cerr<<"HERE "<<i<<' '<<runsum+1<<' '<<tr.size()<<'\n';
		cout<<tr.get(runsum+1)<<' ';
		tr.erase(runsum+1, runsum+1);
		tr.print();
	}
	cout<<'\n';
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);


	#ifndef LOCAL
	#ifdef FIO
		#define fname "order"
		freopen(fname".in", "r", stdin);
		freopen(fname".out", "w", stdout);
	#endif
	#endif

	int t=1;

	#ifdef TESTS
		cin>>t;
	#endif
	while(t--)
	{
		solve();
	}
	return 0;
}