Pagini recente » Cod sursa (job #1222280) | Cod sursa (job #2896811) | Cod sursa (job #1530227) | Cod sursa (job #651819) | Cod sursa (job #1435978)
#include <fstream>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#define int64 long long
#define lsb(x) (-x)&(x)
#define INF numeric_limits<int>::max()
#define mp make_pair
#define pb push_back
using namespace std;
ifstream in("order.in");
ofstream out("order.out");
vector<int> aib;
int n;
void mark(int pos,int val)
{
for(int i=pos;i<=n;i+=lsb(i))
aib[i]+=val;
}
int qsum(int pos)
{
int s=0;
for(int i=pos;i>0;i-=lsb(i))
s+=aib[i];
return s;
}
int getpos(int x)
{
int left=1,right=n;
while(left<=right)
{
int mid=(left+right)/2;
int sum=qsum(mid);
if(sum==x)return mid;
else if(sum>x)right=mid-1;
else left=mid+1;
}
return -1;
}
int main()
{
in>>n;
aib=vector<int> (n+1);
for(int i=1;i<=n;i++)mark(i,1);
for(int pos=1,step=1;step<=n;step++)
{
int s=qsum(n)-qsum(pos),st=step;
if(st>=s)
{
while(st>s)
{
st-=s;
s=qsum(n);
}
pos=getpos(st);
}
else pos=getpos(st+qsum(pos));
mark(pos,-1);
out<<pos<<' ';
}
return 0;
}