Pagini recente » Cod sursa (job #1708286) | Cod sursa (job #1222239) | Cod sursa (job #1025891) | Cod sursa (job #2134181) | Cod sursa (job #3177780)
#include <bits/stdc++.h>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int n,no_of_one,pos;
vector<int>aib;
void update(int node,int value)
{
for(; node<=n; node+=node&(-node))
aib[node]+=value;
}
int query(int node)
{
int ans=0;
for(; node>0; node-=node&(-node))
ans+=aib[node];
return ans;
}
int magical_binary_search(int value)
{
int ans=0,curr_sum=0;
for(int step=(1<<30); step>0; step>>=1) ///we search for the last position with the sum strictly smaller than value
if(ans+step<=n && curr_sum+aib[ans+step]<value)
{
ans+=step;
curr_sum+=aib[ans];
}
if(ans+1>n || query(ans+1)!=value) ///if the sum for the next position isn't equal to value we return -1
return -1; ///not gonna happen in this problem
return ans+1;
}
int main()
{
f>>n;
aib.resize(n+1);
///later we want to find the ith 1,
///so its easier to start with all elements being 1
for(int i=1; i<=n; i++)
update(i,1);
no_of_one=1;
for(int i=1; i<n; i++)
{
pos=magical_binary_search((no_of_one+i)%(n-i+1)); /// we search for the (position of current one + i)th one in a circular array,
/// hence, we take (position of current one + i)%(n-i+1) to find it in our normal array
update(pos,-1); /// we update that position with -1 because it can't be used anymore
no_of_one=query(pos); /// we find the number of ones up until pos
g<<pos<<' ';
}
pos=magical_binary_search(1);
update(pos,-1); /// just for fun
g<<pos<<' ';
return 0;
}