Submission #239282

#	Time	Username	Problem	Language	Result	Execution time	Memory
239282		aggu_01000101	Carnival (CEOI14_carnival)	C++14	100 / 100	13 ms	384 KiB

carnival

#include <bits/stdc++.h>
#define int long long
#define INF 1000000000000000
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define x(p) p.first
#define y(p) p.second
#define MOD 998244353
using namespace std;
int q(vector<int> &curr, int i, int l, int r){
    cout<<((r-l+1) + 1)<<" ";
    for(int j = l;j<=r;j++) cout<<curr[j]<<" ";
    cout<<i<<endl;
    int tr;
    cin>>tr;
    return tr;
}
signed main(){
    int n;
    cin>>n;
    int arr[n+1];
    int nextdist = 2;
    arr[1] = 1;
    vector<int> curr = {1};
    //curr contains all distinct 'dresses' between 1 and i-1
    //If i is distinct, we add it to curr
    for(int i = 2;i<=n;i++){
        int dist = q(curr, i, 0, curr.size()-1);
        if(dist == nextdist){
            arr[i] = nextdist++;
            curr.push_back(i);
            continue;
        }
        //There is a duplicate
        int lo = 0;
        int hi = curr.size() - 1;
        while(lo<hi){
            int mid = mid(lo, hi);
            dist = q(curr, i, lo, mid);
            if(dist == ((mid - lo + 1) + 1)){
                lo = mid + 1;
                continue;
            }
            else hi = mid;
        }

        //lo is the index of the duplicate
        //cout<<"i is same as "<<lo<<endl;
        arr[i] = arr[curr[lo]];
    }
    cout<<"0 ";
    for(int i = 1;i<n;i++) cout<<arr[i]<<" ";
    cout<<arr[n]<<endl;
}
//2 1 2 3 1

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