Submission #1244502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244502		madamadam3	Carnival (CEOI14_carnival)	C++20	0 / 100	25 ms	408 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]);
        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 N) {
        n = N; 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);

    for (int i = 1; i <= n; i++) {
        for (int j = i+1; j <= n; j++) {
            if (i == j) continue;

            int ans = ask(2, vi({i, j}));
            if (ans == 1) dsu.unite(i, j);
        }
    }

    vi ans(n); for (int i = 0; i < n; i++) ans[i] = dsu.find(i+1);
    answer(ans);
    return 0;
}

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