Cod sursa(job #2672892)

Utilizator OvidRata Ovidiu Ovid Data 15 noiembrie 2020 12:25:05
Problema Order Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 kb
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int t, n, m, k, a[300010], q, l, r;


ifstream fin("order.in"); ofstream fout("order.out");
#define cin fin
#define cout fout




struct it{
    int p, c, sz;

    it *l, *r;

    it(int p, int c, it* l, it*r){
        this->p=p;
        this->c=c;
        this->l=l;
        this->r=r;
    }

} *R;



int szof(it*t){
    if(!t){return 0;}
    return t->sz;
}

void recalc(it*t){
    if(!t){return;}
    t->sz=szof(t->l)+szof(t->r)+1;
}

it* create(int p, int c, it*l, it*r){
    it *t=new it(p, c, l, r);
    recalc(t);
    return t;
}


void merge(it*&t, it*l, it*r){
    if((!l)||(!r)){t=(l)?(l):(r); recalc(t); return;  }

    if(l->p>r->p){
        merge(l->r, l->r, r); t=l;
    }
    else{
        merge(r->l, l, r->l); t=r;
    }
    recalc(t);
    return;
}


void split(it*t, it*&l, it*&r, int pos, int add){
    if(!t){r=l=0; return;}

    int cr=szof(t->l)+1+add;
    if(pos<cr){
        split(t->l, l, t->l, pos, add); r=t;
    }
    else{
        split(t->r, t->r, r, pos, cr); l=t;
    }
    recalc(t);
}




void insert(it*&t, int pos, int c){
    it* newt=create(rand(), c, NULL, NULL);
    it *n1;
    split(t, t, n1, pos-1, 0);
    merge(t, t, newt);
    merge(t, t, n1);
}

int erase(it*& t, int pos){
    it *n1, *n2;
    split(t, t, n1, pos-1, 0);

    //if(!n1){cout<<"bt! "<<flush;}
    //else{cout<<n1->c<<" "<<flush;}

    split(n1, n1, n2, 1, 0);

    //if(!n1){cout<<"b!"<<flush;}

    int res=n1->c;
    merge(t, t, n2);
    return res;
}






int32_t main(){
INIT
srand((unsigned)(time(0)));

cin>>n;
for(int i=1; i<=n; i++){
    insert(R, i, i);
//    cout<<i<<" "<<flush;
}

int cr=1;

for(int i=1; i<=n; i++){
    int pos=(((cr+i)%(n-i+1))==0)?((n-i+1) ):(((cr+i)%(n-i+1)) );
    //cout<<pos<<"p "<<flush;
    if( (n-i)>0ll ){cr= (( (pos-1)%(n-i) )==0)?(n-i):( (pos-1)%(n-i) );}
    int k=erase(R, pos);
    cout<<k<<" "<<flush;
}




return 0;
}