Pagini recente » Cod sursa (job #850212) | Cod sursa (job #2731210) | Cod sursa (job #1649999) | Cod sursa (job #3002065) | Cod sursa (job #2777096)
#include <fstream>
#include <vector>
using namespace std;
template <class T_Data, class T_Over>
class FenwickTree{
public:
vector<T_Data> data;
T_Over GetSum(int i)
{
T_Over sum = 0;
++i;
while(i > 0)
{
sum += data[i];
i -= (i & (-i));
}
return sum;
}
void Add(int i, T_Data delta)
{
++i;
while(i < data.size())
{
data[i] += delta;
i += (i & (-i));
}
}
FenwickTree(int capacity) : data(capacity + 1, 0){}
};
int binary(int n, int target, FenwickTree<int,int> aib)
{
int mid, st, dr, out;
st = 1;
dr = out = n;
while(st <= dr)
{
mid = (st + dr) / 2;
if(aib.GetSum(mid) <= target)
{
st = mid + 1;
out = mid;
}
else
dr = mid - 1;
}
return out;
}
int main()
{
ifstream cin ("order.in");
ofstream cout("order.out");
int n, it;
cin >> n;
FenwickTree<int,int> aib = *(new FenwickTree<int,int>(n));
for(int i = 1; i <= n; i++)
aib.Add(i, 1);
int pos = 2;
for(int i = 1; i <= n; i++)
{
pos = (pos + i - 1) % (n - i + 1);
if(pos == 0)
pos = n - i + 1;
for(it = binary(n, pos, aib); aib.GetSum(it) == pos; it--)
;
aib.Add(it + 1, -1);
cout << it + 1 << " ";
}
return 0;
}