Cod sursa(job #2777384)

Utilizator AACthAirinei Andrei Cristian AACth Data 23 septembrie 2021 10:04:34
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.39 kb
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
#define cin f
#define cout g
//#define int long long
const int Max = 3e4 + 1;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int n;
namespace SegmentTree{
    struct Node{
        int val;
    }tree[4*Max];
    int rev[Max];
    Node merge(Node n1, Node n2)
    {
        Node ans;
        ans.val = n1.val+n2.val;
        return ans;
    }
    //remember to call init and update n
    int n;
    void init(int where , int left, int right)
    {
        if(left == right)
        {
            tree[where].val = 1;
            rev[left] = where;
            return;
        }
        int mid = (left + right) / 2;
        init(2*where,left,mid);
        init(2*where + 1,mid+1,right);
        tree[where] = merge(tree[2*where],tree[2*where+1]);
    }
    void propagate(int where)
    {
        if(where)
        {
            tree[where] = merge(tree[2*where],tree[2*where+1]);
            propagate(where / 2);
        }
    }
    void Update(int pos,int val)
    {
        int pos_in_tree = rev[pos];
        tree[pos_in_tree].val = val;
        propagate(pos_in_tree / 2);
    }
    int left_limit,right_limit;
    vector<Node> elem;
    void QueryRange(int where, int left, int right)
    {
        if(left_limit <= left and right <= right_limit)
        {
            //sunt pe o pozitie pe care pot considera nodul
            elem.push_back(tree[where]);
            return;
        }
        int mid = (left + right) / 2;
        if(left_limit <= mid)
            QueryRange(2*where,left,mid);
        if(mid + 1 <= right_limit)
            QueryRange(2*where + 1, mid + 1,right);
    }
    int Query(int left, int right)
    {
        if(left > right)
            return 0;
        left_limit = left;
        right_limit = right;
        elem.clear();
        QueryRange(1,1,n);
        if(elem.empty())
            return 0 ;
        Node ans = elem[0];
        for(int i = 1; i < elem.size();i++)
            ans = merge(ans,elem[i]);
        return ans.val;
    }
    int First_True(function < bool (int) > fun, int left, int right)
    {
        while(left < right)
        {
            int mid = (left + right) / 2;
            fun(mid)?right = mid : left = mid + 1;
        }
        return left;
    }
    int find_next(int where, int left, int right, int val)
    {
        //ca la problema schi
        tree[where].val --;
        if(left == right)
            return left;
        int mid = (left + right) / 2;
        if(tree[2*where].val >= val)
            return find_next(2*where,left,mid ,val);
        else
            return find_next(2*where+1,mid + 1,right,val - tree[2*where].val);

    }

}
void read()
{
	f>>n;

}
void solve()
{
    SegmentTree::init(1,1,n);
    SegmentTree::n = n;
    int i;
    int poz = 2;
    for(i=1;i<=n;i++)
    {
        int ramase = SegmentTree::tree[1].val;
        int search = (poz + i - 1)%ramase;
        if(search == 0)
            search = ramase;
        poz = search;
        //trebuie sa gasesc  a search - a ramasa
        cout<<SegmentTree::find_next(1,1,n,search)<<' ';

    }
}
void restart()
{
	
}
int32_t main()
{
    nos();
        read();
        solve();
        restart();
    
    return 0;
}