Submission #683823

#	Time	Username	Problem	Language	Result	Execution time	Memory
683823		Tenis0206	Abracadabra (CEOI22_abracadabra)	C++11	0 / 100	7 ms	596 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct queries
{
    int t,poz,cnt;
};

struct Node
{
    Node *st, *dr;
    int prior, sz;
    int val, Max;
};

int n,m;
int v[100005];
queries q[1000005];

Node nil[2];
Node *T = &nil[0];
Node *I = &nil[1];

int rez[1000005];

mt19937 my_rand(time(NULL));

Node *modfiu(Node *nod, bool care, Node *son)
{
    if(care==0)
    {
        nod -> st = son;
    }
    else
    {
        nod -> dr = son;
    }
    nod -> sz = nod -> st -> sz + 1 + nod -> dr -> sz;
    nod -> Max = nod -> val;
    nod -> Max = max(nod -> Max, nod->st->Max);
    nod -> Max = max(nod -> Max, nod->dr->Max);
    return nod;
}

Node *join(Node *st, Node *dr, bool care)
{
    if(st==&nil[care])
    {
        return dr;
    }
    if(dr==&nil[care])
    {
        return st;
    }
    if(st->prior >= dr->prior)
    {
        return modfiu(st,1,join(st->dr,dr,care));
    }
    else
    {
        return modfiu(dr,0,join(st,dr->st,care));
    }
}

pair<Node*,Node*> split(Node *nod, int k, bool care)
{
    if(nod==&nil[care])
    {
        return {&nil[care],&nil[care]};
    }
    if(nod->st->sz>=k)
    {
        auto t = split(nod->st,k,care);
        return {t.first,modfiu(nod,0,t.second)};
    }
    else
    {
        auto t = split(nod->dr,k - nod->st->sz - 1,care);
        return {modfiu(nod,1,t.first),t.second};
    }
}

pair<Node*,Node*> split_by_val(Node *nod, int val, bool care)
{
    if(nod==&nil[care])
    {
        return {&nil[care],&nil[care]};
    }
    if(nod->st->Max > val)
    {
        auto t = split(nod->st,val,care);
        return {t.first,modfiu(nod,0,t.second)};
    }
    else
    {
        auto t = split(nod->dr,val,care);
        return {modfiu(nod,1,t.first),t.second};
    }
}

int get_cnt_first(Node *nod, bool care)
{
    if(nod->st == &nil[care])
    {
        return nod -> sz;
    }
    return get_cnt_first(nod->st,care);
}

int query(Node *nod, int poz)
{
    auto t = split(nod,poz-1,0);
    auto t2 = split(t.second,1,0);
    int val = t2.first -> val;
    T = join(t.first,join(t2.first,t2.second,0),0);
    return val;
}

int find_new_poz(int val)
{
    if(I->Max==val)
    {
        return I -> sz;
    }
    auto t = split_by_val(I,val,1);
    int rez = t.first -> sz - 1;
    I = join(t.first,t.second,1);
    return rez;
}

void debug()
{
    for(int i=1;i<=n;i++)
    {
        cerr<<query(T,i)<<' ';
    }
    cerr<<'\n';
}

/// 1 2 3 4 5 6

bool next_perm()
{
    auto t = split(I,n/2,1);
    int first = t.first -> sz + 1;
    int cnt = get_cnt_first(t.second,1);
    auto t2 = split(t.second,cnt,1);
    t2.first -> sz = n / 2 - t.first -> sz;
    I = join(t.first,join(t2.first,t2.second,1),1);

    auto pref = split(T,n/2,0);
    auto buc = split(pref.second,first + cnt - 1 - (n / 2),0);
    /// pref.first = 1 - n / 2;
    /// buc.first = bucata mutata
    /// buc.second = sufixul sirului
    int poz = n / 2 + 1;
    bool ok = false;
    while(poz<=first+cnt-1)
    {
        int val = query(buc.first,1);
        pair<Node*,Node*> aux;
        if(buc.first -> Max == val)
        {
            aux.first = buc.first;
            aux.second = &nil[0];
        }
        else
        {
            aux = split_by_val(buc.first,val,0);
        }
        int new_poz = find_new_poz(val);
        if(new_poz+1!=poz)
        {
            ok = true;
        }
        t = split(I,new_poz,1);
        I = join(t.first,join(new Node{&nil[1],&nil[1],my_rand(),aux.first -> sz,val,val},t.second,1),1);
        t = split(pref.first,new_poz,0);
        poz += aux.first -> sz;
        pref.first = join(t.first,join(aux.first,t.second,0),0);
        buc.first = aux.second;
    }
    T = join(pref.first,join(buc.first,buc.second,0),0);
    debug();
    return ok;
}

void first_perm()
{
    vector<int> aux;
    int st = 1;
    int dr = n / 2 + 1;
    while(st<=n/2 && dr<=n)
    {
        if(v[st]<v[dr])
        {
            aux.push_back(v[st++]);
        }
        else
        {
            aux.push_back(v[dr++]);
        }
    }
    while(st<=n/2)
    {
        aux.push_back(v[st++]);
    }
    while(dr<=n)
    {
        aux.push_back(v[dr++]);
    }
    for(int i=1;i<=n;i++)
    {
        v[i] = aux[i - 1];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    for(int i=1; i<=m; i++)
    {
        cin>>q[i].t>>q[i].poz;
        q[i].cnt = i;
    }
    auto cmp = [](queries a, queries b)
    {
        return a.t < b.t;
    };
    sort(q+1,q+m+1,cmp);

    int poz = 1;
    while(q[poz].t == 0)
    {
        rez[q[poz].cnt] = v[q[poz].poz];
        ++poz;
    }
    first_perm();

    int first = v[1];
    int nr = 0;
    for(int i=1; i<=n; i++)
    {
        if(v[i] > first || i == n / 2 + 1)
        {
            if(i!=1)
            {
                I = join(I,new Node{&nil[1],&nil[1],my_rand(),nr,first,first},1);
            }
            first = v[i];
            nr = 0;
        }
        ++nr;
        T = join(T,new Node{&nil[0],&nil[0],my_rand(),1,v[i],v[i]},0);
    }
    for(int t=1; t<=n; t++)
    {
        while(poz<=m && q[poz].t==t)
        {
            rez[q[poz].cnt] = query(T,q[poz].poz);
            ++poz;
        }
        bool ok = next_perm();
        if(!ok)
        {
            break;
        }
    }
    for(int i=poz; i<=m; i++)
    {
        rez[q[i].cnt] = query(T,q[i].poz);
    }
    for(int i=1; i<=m; i++)
    {
        cout<<rez[i]<<'\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'bool next_perm()':
Main.cpp:178:63: warning: narrowing conversion of 'my_rand.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()()' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  178 |         I = join(t.first,join(new Node{&nil[1],&nil[1],my_rand(),aux.first -> sz,val,val},t.second,1),1);
      |                                                        ~~~~~~~^~
Main.cpp: In function 'int main()':
Main.cpp:257:60: warning: narrowing conversion of 'my_rand.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()()' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  257 |                 I = join(I,new Node{&nil[1],&nil[1],my_rand(),nr,first,first},1);
      |                                                     ~~~~~~~^~
Main.cpp:263:52: warning: narrowing conversion of 'my_rand.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()()' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  263 |         T = join(T,new Node{&nil[0],&nil[0],my_rand(),1,v[i],v[i]},0);
      |                                             ~~~~~~~^~
Main.cpp:223:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  223 |     freopen("nr.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:224:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |     freopen("nr.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25