Cod sursa(job #2413693)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 23 aprilie 2019 17:15:39
Problema Order Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("order.in");
ofstream g("order.out");

namespace Treap{
    struct Node{
        Node *l=0,*r=0;
        int x=0;
        int y=0;
        int sz=0;
        Node (int _x=0): x(_x), y(rand()), sz(1) {}
        void recalc();
    };
    int cnt(Node* t){
        if(!t)return 0;
        return (t->sz);
    }
    void Node::recalc(){
        sz=cnt(l)+cnt(r)+1;
    }
    pair<Node*,Node*> split(Node* t,int k){
        if(!t)return {};

        t->recalc();
        if(cnt(t->l)>=k){
            auto pa=split(t->l,k);
            t->l=pa.second;
            t->recalc();
            return {pa.first,t};
        }else{
            auto pa=split(t->r,k-cnt(t->l)-1);
            t->r=pa.first;
            t->recalc();
            return {t,pa.second};
        }
    }
    Node* join(Node* l,Node *r){
        if(!l)return r;
        if(!r)return l;
        l->recalc();
        r->recalc();
        if(l->y > r->y)
        {
            l->r=join(l->r,r);
            l->recalc();
            return l;
        }else{
            r->l=join(l,r->l);
            r->recalc();
            return r;
        }
    }
    Node* insert(Node* t,int k,int e){
        auto pa=split(t,k-1);
        return join(pa.first,join(new Node(e),pa.second));
    }
    Node* erase(Node* t,int k){
        auto pa=split(t,k-1);
        auto u =split(pa.second,1);
        return join(pa.first,u.second);
    }
    int acces(Node* t,int k){
        if(!t)return -1;
        t->recalc();
        if(cnt(t->l)+1==k) return (t->x);
        if(cnt(t->l)>=k) return acces(t->l,k);
        return acces(t->r,k-cnt(t->l)-1);
    }
}

int main()
{
    srand(time(0));
    Treap::Node *root=0;
    int n;f>>n;
    for(int i=1;i<=n;i++)
        root=Treap::insert(root,i,i);
    int lastpoz=1;
    for(int i=1;i<=n;i++)
    {
        lastpoz+=i;
//        while(lastpoz>n-i+1)
//            lastpoz-=n-i+1;
        lastpoz=(lastpoz-1)%(n-i+1)+1;
        g<<Treap::acces(root,lastpoz)<<' ';
        root=Treap::erase(root,lastpoz);
        lastpoz--;
    }
    return 0;
}