oj.uz

Submission #1042781

# Submission time Handle Problem Language Result Execution time Memory
1042781 2024-08-03T11:25:08 Z SyedSohaib_123 Carnival (CEOI14_carnival) C++17
100 / 100
 9 ms 600 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 5 ms 464 KB Output is correct
4 Correct 9 ms 340 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 7 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 4 ms 344 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 7 ms 464 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 6 ms 460 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 7 ms 600 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 7 ms 344 KB Output is correct