Pagini recente » Cod sursa (job #2695482) | Cod sursa (job #502552) | Cod sursa (job #1072137) | Cod sursa (job #2286651) | Cod sursa (job #2835404)
#include <iostream>
#include <fstream>
#define dbb cout << "blockind: " << blockind << '\n';
#define dbj cout << "j: " << j << '\n';
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
const int BLOCKBITS = 7, BLOCKSIZE = 127, NRBLOCKS = 300, NMAX = 30000;
bool elim[NMAX];
int blocks[NRBLOCKS];
int getBlock(int pos);
int getFirst(int block);
int getLast(int block);
void rmv(int pos);
void initBlocks(int n);
int main()
{
int i, j, n, r, x, blockind, lpos, lastblock;
fin >> n;
initBlocks(n);
j = 0;
r = n;
lastblock = getBlock(n);
for (i = 1; i <= n; i++) {
x = i % r;
while (x) {
blockind = getBlock(j);
lpos = min(getLast(blockind), n - 1);
while (x && j <= lpos) {
x -= (1 - elim[j]);
j++;
}
j--;
if (!x)
break;
if (blockind == lastblock)
blockind = 0;
else
blockind++;
while (x >= blocks[blockind] && blockind <= lastblock) {
x -= blocks[blockind];
j = getLast(blockind);
blockind++;
}
if (blockind > lastblock)
blockind = 0;
if (x)
j++;
}
rmv(j);
fout << j + 1 << " ";
r--;
}
return 0;
}
int getBlock(int pos) {
return pos >> BLOCKBITS;
}
int getFirst(int block) {
return block << BLOCKBITS;
}
int getLast(int block) {
return (block << BLOCKBITS) + BLOCKSIZE;
}
void rmv(int pos) {
int block = getBlock(pos);
blocks[block]--;
elim[pos] = 1;
}
void initBlocks(int n) {
int mxBlock = getBlock(n);
int i;
for (i = 0; i < mxBlock; i++)
blocks[i] = BLOCKSIZE + 1;
blocks[mxBlock] = n - getFirst(i) + 1;
}