Pagini recente » Cod sursa (job #3203971) | Cod sursa (job #644893) | Cod sursa (job #3175856) | Cod sursa (job #2216163) | Cod sursa (job #2835853)
#include <iostream>
#include <fstream>
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 getNext(int pos, int lastblock);
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;
j = 0, r = n;
n--;
lastblock = getBlock(n);
initBlocks(n);
for (i = 1; i <= n + 1; i++) {
j = getNext(j, n);
x = i % r;
while (x) {
if (j > n)
j = 0;
blockind = getBlock(j);
lpos = min(getLast(blockind), n);
while (x && j <= lpos) {
x -= (1 - elim[j]);
j++;
}
j--;
if (blockind == lastblock)
blockind = 0;
else
blockind++;
while (x >= blocks[blockind] && blockind <= lastblock) {
x -= blocks[blockind];
j = min(getLast(blockind), n);
blockind++;
}
if (x)
j++;
if (blockind > lastblock)
blockind = 0;
}
if (j == n + 1)
j = 0;
rmv(j);
fout << j + 1 << " ";
r--;
}
return 0;
}
int getNext(int pos, int n) {
pos++;
if (pos == n + 1)
pos = 0;
int lastblock = getBlock(n);
int block = getBlock(pos);
if (blocks[block]) {
while (elim[pos])
pos++;
}
else {
for (block; block <= lastblock && !blocks[block]; block++);
if (block == lastblock + 1)
for (block = 0; !blocks[block]; block++);
pos = getFirst(block);
while (elim[pos])
pos++;
}
return pos;
}
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(mxBlock) + 1;
}