Pagini recente » Cod sursa (job #2179925) | Cod sursa (job #1702118) | Cod sursa (job #1383967) | Cod sursa (job #538765) | Cod sursa (job #3261663)
#include <fstream>
#include <set>
using namespace std;
const int N = 30005;
int n, aib[N], remaining;
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 sum = 0;
for (int i = pos; i >= 1; i -= i & -i)
sum += aib[i];
return sum;
}
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 step) {
if (step == remaining)
return *active.begin();
step %= remaining;
int queryPos = Query(pos);
int suffix = Query(n) - queryPos;
if (suffix >= step) {
int left = pos, right = n, result = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (Query(mid) - queryPos >= step) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return Find(result);
} else {
int left = 1, right = pos, result = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (Query(mid) + suffix >= step) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return Find(result);
}
}
int main() {
ifstream fin("order.in");
ofstream fout("order.out");
fin >> n;
for (int i = 1; i <= n; ++i) {
Update(i, 1);
active.insert(i);
}
remaining = n;
int pos = 1;
for (int step = 1; step <= n; ++step) {
pos = Next(pos, step);
--remaining;
Update(pos, -1);
active.erase(pos);
fout << pos << ' ';
}
fin.close();
fout.close();
return 0;
}