Cod sursa(job #2835853)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 19 ianuarie 2022 12:01:53
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 kb

#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;
}