oj.uz

Submission #933097

# Submission time Handle Problem Language Result Execution time Memory
933097 2024-02-25T03:38:20 Z agg Carnival (CEOI14_carnival) C++17
100 / 100
 14 ms 596 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 444 KB Output is correct
2 Correct 9 ms 444 KB Output is correct
3 Correct 5 ms 448 KB Output is correct
4 Correct 3 ms 444 KB Output is correct
5 Correct 8 ms 436 KB Output is correct
6 Correct 9 ms 444 KB Output is correct
7 Correct 8 ms 440 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 444 KB Output is correct
2 Correct 11 ms 596 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 5 ms 444 KB Output is correct
5 Correct 8 ms 440 KB Output is correct
6 Correct 12 ms 444 KB Output is correct
7 Correct 11 ms 440 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 448 KB Output is correct
2 Correct 14 ms 344 KB Output is correct
3 Correct 10 ms 444 KB Output is correct
4 Correct 3 ms 444 KB Output is correct
5 Correct 8 ms 440 KB Output is correct
6 Correct 8 ms 440 KB Output is correct
7 Correct 9 ms 444 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 436 KB Output is correct
2 Correct 12 ms 440 KB Output is correct
3 Correct 5 ms 448 KB Output is correct
4 Correct 3 ms 448 KB Output is correct
5 Correct 9 ms 436 KB Output is correct
6 Correct 6 ms 440 KB Output is correct
7 Correct 11 ms 440 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 440 KB Output is correct
2 Correct 13 ms 440 KB Output is correct
3 Correct 8 ms 444 KB Output is correct
4 Correct 6 ms 444 KB Output is correct
5 Correct 6 ms 444 KB Output is correct
6 Correct 4 ms 448 KB Output is correct
7 Correct 3 ms 448 KB Output is correct