Submission #1042781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042781		SyedSohaib_123	Carnival (CEOI14_carnival)	C++17	100 / 100	9 ms	600 KiB

carnival

#include<bits/stdc++.h>



using namespace std;



#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")



#define str string
#define append push_back
#define vi vector<int>
#define int long long
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
// #define endl '\n'
#define all(ls) ls.begin(),ls.end()
#define sorted(ls) sort(ls.begin(),ls.end());
#define reversed(ls) reverse(ls.begin(),ls.end());
#define print(n) for(auto i:n)cout<<i<<' ';cout<<endl;
#define input(n,ls,m) vector<n>ls(m);for(int i=0;i<m;i++)cin>>ls[i];
#define len(s) s.size()
#define ff first
#define ss second


int const N=3e5+100;
int const LG=21;



int mod=1e9+7;
int mod1=998244353;



int sum_(vector<int>ls){int s=0;for(auto i:ls)s+=i;return s;}
int min(int a,int b){if (a>b){return b;}return a;}
int max(int a,int b){if (a<b){return b;}return a;}



//......................................tHe ReaL cOdE beGinS HerE......................................//  



int c[N];



int q(int a,int b){
    cout<<b-a+1<<' ';
    for(int i=a;i<=b;i++) cout<<i<<' ';
    cout<<endl;
    int x;
    cin>>x;
    return x;
}



int get(int a,int b){
    set<int>s;
    for(int i=a;i<=b;i++){
        s.insert(c[i]);
    }
    return s.size();
}



void solve(){
    int n;
    cin>>n;
    c[1]=1;
    int mex=2;
    for(int i=2;i<=n;i++){
        int l=0,r=i,m;
        while(l+1<r){
            m=(l+r)/2;
            int x=q(m,i);
            int y=get(m,i-1);
            if(x>y){
                r=m;
            }
            else{
                l=m;
            }
        }
        if(l==0) c[i]=mex,mex++;
        else c[i]=c[l];
    }
    cout<<0<<' ';
    for(int i=1;i<=n;i++) cout<<c[i]<<' ';
    cout<<endl;
} 

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
        solve();
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20