Cod sursa(job #2863840)

Utilizator 100pCiornei Stefan 100p Data 7 martie 2022 12:02:54
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <bits/stdc++.h>
#define ull unsigned long long
#define FILES freopen("order.in","r",stdin);\
              freopen("order.out","w",stdout);
#define CMAX 15485863
#define fastio std::ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);
#define mp make_pair
#define INF 1e18
#define mod 1000000007
#define ll long long
#define SMAX 300
#define MAX 200000
#define pb push_back
#define add emplace_back
#define void inline void
#define int ll

using namespace std;
int n,tree[MAX*4+5],cat,ot;
void update(int st,int dr,int node,int pz,int val)
{
    if(st == dr)
    {
        tree[node] += val;
        return;
    }
    int mid = (st + dr) >> 1;
    if(pz <= mid) update(st,mid,(node<<1)+1,pz,val);
    else update(mid+1,dr,(node<<1)+2,pz,val);
    tree[node] = tree[(node<<1)+1] + tree[(node<<1)+2];
}
void query(int st,int dr,int node,int ot)
{
    if(st == dr)
    {
        cat = st;
        return;
    }
    int mid = (st + dr) >> 1;
    if(tree[(node<<1)+1] >= ot)
        query(st,mid,(node<<1)+1,ot);
    else
        query(mid+1,dr,(node<<1)+2,ot - tree[(node<<1)+1]);
}
signed main()
{
    fastio
    FILES
    cin >> n;
    for(int i = 1;i <= n; ++i)
        update(1,n,0,i,1);
    int cnt = 2, x = 1, e = n;
    while(e)
    {
        cnt %= e;
        if(!cnt) cnt = e;
        int pos = cnt;
        query(1,n,0,pos);
        update(1,n,0,cat,-1);
        e--;
        cnt += x;
        cout << cat << ' ';
        x++;
    }
}