Submission #933097

#	Time	Username	Problem	Language	Result	Execution time	Memory
933097		agg	Carnival (CEOI14_carnival)	C++17	100 / 100	14 ms	596 KiB

carnival

#include <iostream>
#include <vector>

using namespace std;

const int MAX_NODES = 1005;

int parent[MAX_NODES];
int nodeSize[MAX_NODES];

// Initialize parent and size arrays
void initialize(int n) {
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
        nodeSize[i] = 1;
    }
}

// Find operation with path compression
int find(int node) {
    if (node == parent[node]) {
        return node;
    }
    return parent[node] = find(parent[node]);
}

// Merge operation with union by size
void merge(int x, int y) {
    x = find(x);
    y = find(y);

    if (x == y) {
        return;
    }

    if (nodeSize[x] < nodeSize[y]) {
        parent[x] = y;
        nodeSize[y] += nodeSize[x];
    } else {
        parent[y] = x;
        nodeSize[x] += nodeSize[y];
    }
}

// Query function to interact with the judge
int query(const vector<int>& indices) {
    cout << indices.size();
    for (int index : indices) {
        cout << ' ' << index;
    }
    cout << endl;

    int answer;
    cin >> answer;
    return answer;
}

int main() {
    int numNodes;
    cin >> numNodes;

    initialize(numNodes);

    for (int i = 1; i <= numNodes; ++i) {
        vector<int> indices;
        for (int j = 1; j <= i - 1; ++j) {
            indices.push_back(j);
        }
        int diffWithout = (indices.empty() ? 0 : query(indices));
        indices.push_back(i);
        int diffWith = query(indices);

        if (diffWith == diffWithout) {
            int left = 1;
            int right = i - 1;

            while (left <= right) {
                int mid = (left + right) / 2;

                vector<int> prefix;
                for (int j = 1; j <= mid; ++j) {
                    prefix.push_back(j);
                }
                diffWithout = query(prefix);

                prefix.push_back(i);
                diffWith = query(prefix);

                if (diffWith == diffWithout) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            merge(left, i);
        }
    }

    int compressed[MAX_NODES];
    int currentColor = 0;

    for (int i = 1; i <= numNodes; ++i) {
        if (i == find(i)) {
            compressed[i] = ++currentColor;
        }
    }

    cout << 0;
    for (int i = 1; i <= numNodes; ++i) {
        cout << ' ' << compressed[find(i)];
    }
    cout << endl;

    return 0;
}

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