Submission #1244514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244514		madamadam3	사육제 (CEOI14_carnival)	C++20	100 / 100	5 ms	456 KiB

carnival

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
const bool LOCAL = false;
const int N = 5; vector<int> COLOURS = {1, 2, 1, 3, 2}; int queries = 0;

int ask(int k, vi people) {
    queries++;
    
    if (LOCAL) {
        set<int> tl;
        for (auto &p : people) tl.insert(COLOURS[p-1]);
        return tl.size();
    } else {
        cout << k; for (auto &el : people) cout << " " << el;
        cout << endl;

        int ans; cin >> ans;
        return ans;
    }
}

void answer(vi colour) {
    if (LOCAL) {
        bool fine = true;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (COLOURS[i] == COLOURS[j] && colour[i] != colour[j]) fine = false;
                if (COLOURS[i] != COLOURS[j] && colour[i] == colour[j]) fine = false;
            }
        }
        
        cout << (fine ? "Program gave correct answer.\n" : "Program gave incorrect answer.\n");
        cout << "Took " << queries << " queries.\n";
        cout << "Program output:"; for (auto &el : colour) cout << " " << el; cout << "\n";
    } else {
        cout << "0"; for (auto &el : colour) cout << " " << el;
        cout << endl;
    }
}

struct DSU {
    int n; vi par, siz;
    DSU() {};
    DSU(int nv) {
        n = nv; par.resize(n); siz.assign(n, 1);
        iota(par.begin(), par.end(), 0);
    } 
    int find(int v) {
        if (v == par[v]) return v;
        return par[v] = find(par[v]);
    }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a != b) {
            if (siz[b] > siz[a]) swap(a, b);
            par[b] = a;
            siz[a] += siz[b];
        }
    }
};

int main() {
    int n = LOCAL ? N : -1; if (!LOCAL) cin >> n;
    auto dsu = DSU(n+1);
    vector<int> reps(1, 1);

    for (int i = 2; i <= n; i++) {
        int lo = 0, hi = reps.size();

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            vector<int> test(reps.begin(), reps.begin() + mid + 1);
            test.push_back(i);
            int result = ask(test.size(), test);

            if (result != test.size()) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        if (lo == reps.size()) {
            reps.push_back(i);
        } else {
            dsu.unite(reps[lo], i);
        }
    }

    int cc = 1;
    map<int, int> cn;
    
    vi ans(n); for (int i = 0; i < n; i++) {
        if (!cn.count(dsu.find(i+1))) cn[dsu.find(i+1)] = cc++;
        ans[i] = cn[dsu.find(i+1)];
    }
    answer(ans);
    return 0;
}

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