Cod sursa(job #2672897)

Utilizator OvidRata Ovidiu Ovid Data 15 noiembrie 2020 12:51:00
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 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


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 nod{
    int sz, c;
};
nod seg[120000];


void build(int v, int l, int r){
int med=(l+r)/2;
if(l==r){
    seg[v].sz=1; seg[v].c=med; return;
}
build(v*2, l, med); build(v*2+1, med+1, r);
seg[v].sz=(seg[v*2].sz+seg[v*2+1].sz);
}





int erase(int v, int l, int r, int pos, int add){
    int med=(l+r)/2;
    if(add>pos){
        return 0;
    }
    int cr=add+seg[v].sz;

    //cout<<"er: l=="<<l<<" r=="<<r<<" cr=="<<cr<<" pos=="<<pos<<"\n";

    if(cr<pos){return 0;}

    if(l==r){
        seg[v].sz=0; return seg[v].c;
    }
    int res=0;

    if( (add+seg[2*v].sz)>=pos  ){
        res=erase(2*v, l, med, pos, add);
    }
    else{
        res=erase(2*v+1, med+1, r, pos, add+seg[2*v].sz);
    }
    seg[v].sz=(seg[2*v].sz+seg[2*v+1].sz);
    return res;
}



int32_t main(){
INIT
cin>>n;
build(1, 1, n);

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)) );
    if(i!=n){cr=( ((pos-1)%(n-i))==0  )?(n-i):( (pos-1)%(n-i) ); }
    int res=erase(1, 1, n, pos, 0);
    cout<<res<<" ";
}



return 0;
}