Cod sursa(job #1937925)

Utilizator superstar1998Moldoveanu Vlad superstar1998 Data 24 martie 2017 13:53:27
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cctype>

#define pb push_back
#define mp make_pair
#define MAXN 30001
#define DIM 8192

using namespace std;

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

int n,arb[MAXN*4],pas,pos=1,a;
vector<int> sol;

void build(int nod, int st, int dr)
{
    arb[nod]=dr-st+1;
    if(st!=dr)
    {
        int mij=(st+dr)/2;
        build(nod*2,st,mij);
        build(nod*2+1,mij+1,dr);
    }
}

void upd(int nod, int st, int dr)
{
    if(st==dr)
    {
        arb[nod]=0;
        return;
    }
    int mij=(st+dr)/2;
    if(pos<=mij)upd(nod*2,st,mij);
    else upd(nod*2+1,mij+1,dr);
    arb[nod]=arb[nod*2]+arb[nod*2+1];
}

int query1(int nod, int st, int dr, int p)
{
    if(p>=dr)
        return arb[nod];
    int mij=(st+dr)/2;
    if(p<=mij)return query1(nod*2,st,mij,p);
    else return query1(nod*2+1,mij+1,dr,p)+arb[nod*2];
}

void query(int nod, int st, int dr)
{
    if(pas>arb[nod])
    {
        pas-=arb[nod];
        return;
    }
    if(st==dr)
    {
        pas=0;
        sol.pb(st);
        return;
    }
    int mij=(st+dr)/2;
    query(nod*2,st,mij);
    if(pas)query(nod*2+1,mij+1,dr);
}

int main()
{
    f>>n;
    build(1,1,n);
    sol.pb(2);
    pos=2;
    upd(1,1,n);
    for(int i=2;i<=n;i++)
    {
        a=query1(1,1,n,pos);
        pas=(a+i-1)%(n-i+1)+1;
        query(1,1,n);
        pos=sol.back();
        upd(1,1,n);
    }
    for(size_t i=0;i<sol.size();i++)
        g<<sol[i]<<" ";
    return 0;
}