Cod sursa(job #2147537)

Utilizator CammieCamelia Lazar Cammie Data 28 februarie 2018 20:10:25
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>

#define MAXN 30005

using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");

int N, ait[MAXN * 4];

inline void Build(int poz, int st, int dr) {
    if (st == dr) {
        ait[poz] = 1;
        return;
    }
    int mij = (st + dr) / 2;

    Build(poz * 2, st, mij);
    Build(poz * 2 + 1, mij + 1, dr);
    ait[poz] = ait[poz * 2] + ait[poz * 2 + 1];
}

inline void Update(int poz, int st, int dr, int val) {
    if (st == dr) {
        fout << st << " ";
        ait[poz] = 0;
        return;
    }
    int mij = (st + dr) / 2;

    if (val <= ait[poz * 2]) {
        Update(poz * 2, st, mij, val);
    }
    else {
        Update(poz * 2 + 1, mij + 1, dr, val - ait[poz * 2]);
    }
    ait[poz] = ait[poz * 2] + ait[poz * 2 + 1];
}

inline void Read() {
    fin >> N;

    Build(1, 1, N);
}

inline void Solve() {
    int pas = 1, NN = N;

    for (int i = 1; i <= N; i++) {
        pas += i; pas %= NN;
        if (pas == 0)
            pas = NN;
        Update(1, 1, N, pas); pas--; NN--;
    }
}

int main () {
    Read();
    Solve();

    fin.close(); fout.close(); return 0;
}