Submission #1351556

#TimeUsernameProblemLanguageResultExecution timeMemory
1351556kantaponzCarnival (CEOI14_carnival)C++20
100 / 100
3 ms424 KiB
#include <bits/stdc++.h>
using namespace std;

const int nx = 155;

int n, c;
int pa[nx];
int qs[nx];

int fp(int n) {
    if (pa[n] == n) return n;
    return pa[n] = fp(pa[n]);
}

void unite(int u, int v) {
    int pu = fp(u), pv = fp(v);
    if (pu == pv) return;
    pa[pu] = pv;
}

int query(vector<int> q) {
    cout << q.size() << " ";
    for (auto x : q) cout << x << " ";
    cout << endl;
    int ans;
    cin >> ans;
    cout << endl;
    return ans;
}

int main() {
    cin >> n;
    vector<int> q;
    for (int i = 1; i <= n; i++) pa[i] = i, q.push_back(i);
    
    for (int i = 1; i <= n; i++) {
        q.clear();
        qs[i] += qs[i - 1];
        for (int j = 1; j <= i; j++) q.push_back(j);
        if (query(q) + qs[i] == i) continue;
        int l = 1, r = i - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            q.clear();
            q.push_back(i);
            for (int j = 1; j <= mid; j++) q.push_back(j);
            if (query(q) + qs[mid] == mid + 1) l = mid + 1;
            else r = mid;
        }
        //cout << l << " \n";
        qs[i]++;
        unite(l, i);
    }

    vector<int> ans;
    for (int i = 1; i <= n; i++) ans.push_back(fp(i));
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    cout << 0 << " ";
    for (int i = 1; i <= n; i++) {
        int pu = fp(i);
        cout << lower_bound(ans.begin(), ans.end(), pu) - ans.begin() + 1 << " ";
    }
    cout << endl;
    return 0;
}


/*
5
1 2 1 3 2

6
1 1 1 2 3 2

5
1 2 3 2 1
*/
#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...