Submission #436706

#TimeUsernameProblemLanguageResultExecution timeMemory
436706ak2006Carnival (CEOI14_carnival)C++14
100 / 100
13 ms312 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
}
int n = 151;
vi col(n);
int answerQuery(int m,vi&a)
{
    assert(m == (int)a.size());
    cout<<m<<" ";
    for (int i = 0;i<m;i++)cout<<a[i]<<" ";
    cout<<endl;
    int ret;
    cin>>ret;
    return ret;
}
int askQuery(int mid,vi&c,int pos)
{
    vi cur;
    cur.pb(pos);
    for (int i = 0;i<mid;i++)cur.pb(c[i]);
    return answerQuery((int)cur.size(),cur);
}
void solve()
{
    vi cur;
    cur.pb(1);
    int num = 1;
    vi ans(n + 1);
    ans[1] = num;
    for (int i = 2;i<=n;i++){
        cur.pb(i);
        int val = answerQuery((int)cur.size(),cur);
        if (val != num + 1)cur.pop_back();
        else ans[i] = ++num;
    }
    for (int i = 1;i<=n;i++){
        if (ans[i] != 0)continue;
        int l = 0,r = (int)cur.size(),pos = 0;//binary search for the last
        //point such that the elements up to that point do not the colour of i
        while (l <= r){
            int mid = (l + r)/2;
            int val = askQuery(mid,cur,i);
            //if (i == 3)cout<<mid<<" "<<val<<endl;
            if (val == mid + 1){
                pos = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        //if (i == 3)cout<<"HERE "<<pos<<endl;
        ans[i] = ans[cur[pos]];
    }
    cout<<0<<" ";
    for (int i = 1;i<=n;i++)cout<<ans[i]<<" ";
}
int main()
{
    setIO();
    cin>>n;
    //for (int i = 1;i<=n;i++)cin>>col[i];
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...