Cod sursa(job #2777376)

Utilizator AACthAirinei Andrei Cristian AACth Data 23 septembrie 2021 09:50:17
Problema Order Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.68 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 get_nxt_poz(int start, int nxt)
    {
    	int left = start;
        int right = n;
        while(left < right)
        {
            int mid = (left + right) / 2;
            if(Query(start,mid) >= nxt)
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }

}
void read()
{
	f>>n;

}
void solve()
{
    SegmentTree::init(1,1,n);
    SegmentTree::n = n;
}
void restart()
{
	int i;
	int poz = 2;
	for(i=1;i<=n;i++)
	{
        int need = i;
        int maxxscot = SegmentTree::Query(poz,n);
        if(need > maxxscot)
        {
            need -= maxxscot;
            int ramase = n - i + 1;
            if(need %ramase != 0)
                need %= ramase;
            else
                need = ramase;
            int pozz = SegmentTree::get_nxt_poz(1,need);
            SegmentTree::Update(pozz,0);
            g<<pozz<<' ';
            poz = pozz + 1;
        }
        else
        {
            int elimin = SegmentTree::get_nxt_poz(poz,need);
            SegmentTree::Update(elimin,0);
            g<<elimin<<' ';
            poz = elimin + 1;
        }
	}
}
int32_t main()
{
    nos();
        read();
        solve();
        restart();
    
    return 0;
}