Pagini recente » Cod sursa (job #2644864) | Cod sursa (job #1894339) | Cod sursa (job #2044692) | Cod sursa (job #2738009) | Cod sursa (job #3261664)
#include <fstream>
#include <set>
using namespace std;
string const task("order");
ifstream fin(task + ".in");
ofstream fout(task + ".out");
int const N(30005);
int n, aib[N], ramas;
set<int> active;
inline void Update(int pos, int val) {
for (int i = pos; i <= n; i += i & -i)
aib[i] += val;
}
inline int Query(int pos) {
int q = 0;
for (int i = pos; i >= 1; i -= i & -i)
q += aib[i];
return q;
}
inline int Find(int pos) {
auto it = active.lower_bound(pos);
if (it == active.end())
it = active.begin();
return *it;
}
inline int Next(int pos, int add) {
if (add == n)
return *active.begin();
if (add > ramas)
add = add % ramas;
if (add == 0)
add = ramas;
int queryPos = Query(pos);
int capat = Query(n) - queryPos;
if (capat >= add) {
int st = pos, dr = n, res = -1;
while (st <= dr) {
int mid = (st + dr) / 2;
if (Query(mid) - queryPos >= add)
res = mid, dr = mid - 1;
else st = mid + 1;
}
return Find(res);
}
else {
int st = 1, dr = pos, res = -1;
while (st <= dr) {
int mid = (st + dr) / 2;
if (Query(mid) + capat >= add)
res = mid, dr = mid - 1;
else st = mid + 1;
}
return Find(res);
}
}
int main() {
fin >> n;
for (int i = 1; i <= n; ++i) {
Update(i, 1);
active.insert(i);
}
ramas = n;
int pos = 1;
for (int i = 1; i <= n; ++i) {
pos = Next(pos, i);
--ramas;
Update(pos, -1);
active.erase(pos);
fout << pos << ' ';
}
fin.close();
fout.close();
return 0;
}