Submission #1307200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307200		simona1230	Abracadabra (CEOI22_abracadabra)	C++20	0 / 100	915 ms	18480 KiB

Main

#include <bits/stdc++.h>

using namespace std;
int n,q;
int a[200001];
int p[1001][1001];
int t,x;
void read()
{
    cin>>n>>q;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        p[0][i]=a[i];
    }

}

void prec1()
{
    for(int i=1; i<=n; i++)
    {
        int j=1;
        int i1=1,i2=n/2+1;
        while(i1<=n/2||i2<=n)
        {
            if(i1>n/2)p[i][j++]=p[i-1][i2++];
            else if(i2>n)p[i][j++]=p[i-1][i1++];
            else if(p[i-1][i1]<p[i-1][i2])p[i][j++]=p[i-1][i1++];
            else p[i][j++]=p[i-1][i2++];
        }
    }
}

void solve1()
{
    for(int i=1; i<=q; i++)
    {
        int t,id;
        cin>>t>>id;
        cout<<p[min(n,t)][id]<<endl;
    }
}

struct group
{
    int id;
    group() {}
    group(int _id)
    {
        id=_id;
    }

    bool operator<(const group&g)const
    {
        return a[id]<a[g.id];
    }
};

set<group> s;
int b[200001];
int sz[200001];
void solve()
{
    cin>>t>>x;
    int i=1;
    while(i<=n)
    {
        int j=i;
        while(j<=n&&a[j]<=a[i])j++;
        s.insert({i});
        //cout<<i<<" - "<<j-i<<endl;
        sz[i]=j-i;
        i=j;
    }


    //cout<<"here"<<endl;

    auto it=s.begin();
    int cnt=0;
    int br=-1;

    while(cnt<n/2)
    {
        cnt+=sz[it->id];
        //cout<<"! "<<cnt<<endl;
        if(cnt>n/2)
            br=it->id;
        else it++;
    }
    cnt-=sz[it->id];

    //cout<<br<<" > "<<cnt<<endl;

    if(br!=-1)
    {
        int lp=0;
        while(lp<t)
        {
            lp++;
            it=s.find(br);

            int nid=it->id+n/2-cnt;
            sz[nid]=sz[it->id]-(n/2-cnt);

            s.erase(it);
            sz[br]=n/2-cnt;
            s.insert({br});
            s.insert({nid});

            //cout<<"!!!! "<<nid<<" "<<sz[nid]<<" "<<br<<" "<<sz[br]<<endl;

            cnt+=sz[br]+sz[nid];
            bool f=0;
            it=s.find(br);
            while(cnt>n/2)
            {
                cnt-=sz[it->id];
                if(cnt==n/2)f=1;
                else if(cnt<n/2)br=it->id;
                else it--;
            }

            if(f)break;
        }
        /*for(int i=1;i<=n;i++)
            cout<<i<<" 0 "<<sz[i]<<endl;*/

        i=1;
        for(it=s.begin(); it!=s.end(); it++)
        {
            group g=*it;
            int j=sz[g.id];
            //cout<<g.id<<" 0> "<<sz[g.id]<<endl;
            while(j--)
            {
                b[i++]=a[g.id];
                g.id++;
            }
        }
    }
    else cout<<0/0<<endl;

    cout<<b[x]<<endl;
    for(int i=1; i<q; i++)
    {
        cin>>t>>x;
        cout<<b[x]<<endl;
    }

    /*for(int i=1;i<=n;i++)
        cout<<b[i]<<" ";
        cout<<endl;*/
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    read();
    if(n<=1)
    {
        prec1();
        solve1();
    }
    else
    {
        solve();
    }
    return 0;
}

/*
10 0
3 2 7 5 4 6 1 8 9 10
*/

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:143:17: warning: division by zero [-Wdiv-by-zero]
  143 |     else cout<<0/0<<endl;
      |                ~^~

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