Cod sursa(job #2654456)

Utilizator matei123Biciusca Matei matei123 Data 1 octombrie 2020 08:22:07
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("order.in"); ofstream g("order.out");
#define lsb(x) (x&(-x))
int aib[30001],sol[30001],n;
void update(int x,int val)
{	 for(int i=x;i<=n;i+=lsb(i)) aib[i]+=val; }
int query(int x)
{	int S=0;
    for(int i=x;i;i-=lsb(i)) S+=aib[i];
    return S;
}
int cautbin(int x)
{	int S=1,D=n,T=0,Minim=INT_MAX;
    while(S<=D)
    {   int mid=(S+D)/2;
        T=query(mid);
        if(T==x && mid<Minim) Minim=mid;
        else if(T>=x) D=mid-1;
        else S=mid+1;
    }
    return Minim;
}
int mod(int x,int MOD)
{   if(!(x%MOD)) return MOD;
	return x%MOD;
}
int main()
{	f>>n;
	for(int i=1;i<=n;i++) update(i,1);
	int ind=n,p=2;
	for(int x,i=1;i<=n;++i)
	{	--ind;
		x=cautbin(p);
		update(x,-1);
		sol[i]=x;
		p+=i;
		if(ind) p=mod(p,ind);
	}
	for(int i=1;i<=n;++i) g<<sol[i]<<" ";
    g.close(); return 0;
}