Cod sursa(job #1966844)

Utilizator FckingSlayerSlayer99 FckingSlayer Data 15 aprilie 2017 16:48:30
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>
#include <limits.h>
#include <iomanip>

#define nMax 30001
#define pb push_back
#define mkp make_pair
#define x first
#define y second

using namespace std;

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

int n, newOrd, arb[4*nMax];

void build(int node, int st, int dr)
{
    if(st==dr)
    {
        arb[node]=1;
        return;
    }

    int mid=st+(dr-st)/2;
    build(2*node, st, mid);
    build(2*node+1, mid+1, dr);

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

void query(int node, int st, int dr)
{
    if(st==dr)
    {
        fout<<st<<" ";
        arb[node]=0;
        return;
    }

    int mid=st+(dr-st)/2;
    if(arb[2*node]>=newOrd)
        query(2*node, st, mid);
    else
    {
        newOrd-=arb[2*node];
        query(2*node+1, mid+1, dr);
    }
    arb[node]=arb[2*node]+arb[2*node+1];
}

int main()
{
    fin>>n;
    build(1, 1, n);
    int nrOrd=2;
    for(int i=1; i<=n; i++)
    {
        newOrd=nrOrd+i-1;
        newOrd=newOrd%(n-i+1);
        if(newOrd==0)
            newOrd=n-i+1;
        nrOrd=newOrd;
        query(1, 1, n);
    }
}