Cod sursa(job #992699)

Utilizator harababurelPuscas Sergiu harababurel Data 2 septembrie 2013 14:06:10
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <fstream>
#define nmax 30005
using namespace std;

int H[3*nmax];
int n, sol, curent, numarActual, x;

void update(int node, int lo, int hi, int pos, int val) {
    if(lo == hi) {
        H[node] = val;
        return;
    }

    int mid = (lo + hi) >> 1;
    if(pos <= mid) update(2*node, lo, mid, pos, val);
    else           update(2*node+1, mid+1, hi, pos, val);

    H[node] = H[2*node] + H[2*node+1];
}

void query(int node, int lo, int hi, int pos) {
    if(lo == hi) {
        sol = lo;
        return;
    }

    int mid = (lo + hi) >> 1;
    if(pos <= H[2*node]) query(2*node, lo, mid, pos);
    else                 query(2*node+1, mid+1, hi, pos-H[2*node]);
}


int main() {
    ifstream f("order.in");
    ofstream g("order.out");

    f>>n;
    for(int i=1; i<=n; i++) update(1, 1, n, i, 1);

    curent = 2;                                         //ca asa vreau, nu de alta...
    for(int i=1; i<=n; i++) {
        numarActual = H[1];                             //ar trebui sa functioneze si n-i+1

        x = (curent + i - 1) % numarActual;             //trebuie eliminat al x-lea de la inceput

        if(x==0) x = numarActual;
        curent = x;

        query(1, 1, n, x);                              //mai intai il gasesc si il tiparesc
        g<<sol<<" ";

        update(1, 1, n, sol, 0);                        //apoi il elimin
    }


    return 0;
}