Pagini recente » Cod sursa (job #1829657) | Cod sursa (job #356703) | Cod sursa (job #1796434) | Cod sursa (job #541233) | Cod sursa (job #950568)
Cod sursa(job #950568)
#include <fstream>
using namespace std;
#define in "order.in"
#define out "order.out"
#define N 30005
int aib[N], n;
void add (int i, int x) {
while (i <= n) {
aib[i] += x;
i += (i^(i-1)) & i;
}
}
int query (int i) {
int sum = 0;
while (i) {
sum += aib[i];
i -= (i^(i-1)) & i;
}
return sum;
}
int BS (int x) {
int lo = 1, hi = n + 1, sol = 0;
while (lo < hi) {
int mid = (lo + hi) >> 1, tmp = query(mid);
if (tmp == x)
sol = mid;
if (tmp >= x)
hi = mid;
else
lo = mid + 1;
}
return sol;
}
int main () {
ifstream fin (in);
fin >> n;
fin.close();
for (int i = 1; i <= n; ++i)
add (i, 1);
ofstream fout (out);
int c = 1, done = n;
for (int pas = 1; pas <= n; ++pas) {
c += pas;
c = (c - 1) % done + 1;
int mod = BS (c);
fout << mod << " ";
add (mod, -1);
c--;
done--;
}
fout.close();
return 0;
}