Cod sursa(job #828459)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 3 decembrie 2012 19:56:25
Problema Order Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <vector>
#define DN 8005

using namespace std;

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

int n, a[4*DN], p, nr;

void update(int vn, int ls, int ld, int poz, int val)
{
    if(ls == ld)
    {
        a[vn] = val;
        return;
    }

    int m = (ls + ld) >> 1;

    if(poz <= m) update(vn << 1, ls, m, poz, val);
    else update((vn << 1) + 1, m + 1, ld, poz, val);

    a[vn] = a[vn << 1] + a[(vn << 1) + 1];
}

void query(int vn, int ls, int ld, int poz)
{
    if(ls==ld)
    {
        p = ls;
        fout << ls << ' ';
        return;
    }

    int m = (ls + ld) / 2;
    if(nr + a[vn << 1] >= poz) query(vn << 1, ls, m, poz);
    else
    {
        nr += a[vn << 1];
        query((vn << 1) + 1, m + 1, ld, poz);
    }
}

int main()
{

    fin >> n;
    for(int i = 1; i <= n; ++i) update (1, 1, n, i, 1);
    int x = 2;
    for (int i = 1; i <= n; ++i)
    {
        nr = 0;
        query(1, 1, n, x);
        update(1, 1, n, p, 0);
        if(a[1] >= 1) x = (x + i) % a[1];
        if(0 == x) x = a[1];
    }
    fin.close();
    fout.close();
    return 0;
}