Cod sursa(job #1774530)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 9 octombrie 2016 01:12:57
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 50005;

int aib[NMAX];
int n, lst;

inline int lsb(int arg) {
    return arg&-arg;
}

int query(int s) {
    int ind = 1 << 15,
        ant = 0,
        act = 0;

    for(; ind; ind>>=1) {
        if(aib[ant+ind]+act < s) {
            act+=aib[ind+ant];
            ant+=ind; } }
    return ant+1; }

void update(int ind, int val) {
    for(; ind<=(1<<15); ind+=lsb(ind)) {
        aib[ind]+=val; } }

int main(void) {
    ifstream fi("order.in");
    ofstream fo("order.out");
    int x;

    x = 2;
    lst = 2;

    fi >> n;
    for(int i=1; i<=n; ++i) {
        update(i, 1); }

    fo << "2 ";
    for(int i=1; i<n; ++i) {
        update(x, -1);
        lst+= i;
        lst%= n-i;
        if(lst == 0) {
            lst = n-i; }
        x = query(lst);

        fo << x << ' ';
    }
    fo << '\n';
    return 0; }