Cod sursa(job #2835288)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 18 ianuarie 2022 14:15:09
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#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];
                blockind++;
            }
            if (blockind > lastblock)
                blockind = 0;
            if (x)
                j = getFirst(blockind);
        }

        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 - (i << BLOCKBITS);
}