Cod sursa(job #2409202)

Utilizator CharacterMeCharacter Me CharacterMe Data 18 aprilie 2019 19:43:36
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int N, i, S=2;
struct Pair{
    int cnt;
    int ind;
};
class BTree{
    Pair V[120001];
    void Change(int target, int val, int a, int b, int position){
        int mid=(a+b)/2;
        if(a==b){V[position].cnt=val; V[position].ind=target; return;}
        else if(target<=mid) Change(target, val, a, mid, 2*position);
        else Change(target, val, mid+1, b, 2*position+1);
        V[position].cnt=V[2*position].cnt+V[2*position+1].cnt;
        return;
    }
    int Find(int val, int a, int b, int position){
        int mid=(a+b)/2;
        if(a==b) return V[position].ind;
        else if(val<=V[2*position].cnt) return Find(val, a, mid, 2*position);
        else return Find(val-V[2*position].cnt, mid+1, b, 2*position+1);
    }
public:
    void Set(int target, int val){
        Change(target, val, 1, N, 1);
        return;
    }
    void Get(int &val){
        if(val>V[1].cnt) val%=V[1].cnt;
        if(val==0) val+=V[1].cnt;
        int sol=Find(val, 1, N, 1);
        Set(sol, 0);
        fout<<sol<<" ";
        return;
    }
};
BTree Arb;
int main()
{
    fin>>N;
    for(i=1; i<=N; ++i) Arb.Set(i, 1);
    for(i=1; i<=N; ++i){
        S=S+i-1;
        Arb.Get(S);
    }
    return 0;
}