oj.uz

답안 #1009898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009898 2024-06-28T07:29:29 Z giorgi123glm 사육제 (CEOI14_carnival) C++17
0 / 100
 24 ms 600 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

using std::cout;
using std::cin;

vector <int> dsu_arr;

const int dsu_parent (int p) {
    return (dsu_arr[p] == p ? p : dsu_arr[p] = dsu_parent (dsu_arr[p]));
}

inline void dsu_join (int a, int b) {
    a = dsu_parent (a), b = dsu_parent (b);
    if (a != b)
        dsu_arr[b] = a;
}

inline const pair <int, int> chk (vector <int>& v, int L, int R, int I) {
    if (L == R) {
        cout << 2 << ' ' << I << ' ' << v[L] << '\n';
        cout.flush ();

        int t = 0;
        cin >> t;

        if (t == 1)
            dsu_join (I, v[L]);
    } else {
        int res1 = 0, res2 = 0;
        cout << R - L + 1 << ' ';
        for (int j = L; j <= R; j++)
            cout << v[j] << ' ';
        cout << '\n';
        cout.flush();

        cin >> res1;

        cout << R - L + 2 << ' ';
        for (int j = L; j <= R; j++)
            cout << v[j] << ' ';
        cout << I << ' ';
        cout << '\n';
        cout.flush();

        cin >> res2;
        if (res1 == 1)
            for (int j = L + 1; j <= R; j++)
                dsu_join (v[L], v[j]);
        if (res2 == 1)
            dsu_join (v[L], I);
        else if (res1 == res2)
            return {L, R};
    }

    return {-1, -1};
}

int main () {
    int n = 0;
    cin >> n;

    dsu_arr.resize (n + 1);
    
    for (int i = 1; i <= n; i++)
        dsu_arr[i] = i;
    
    vector <bool> checked (n + 1);

    for (int i = 1; i <= n - 1; i++) {
        vector <int> v;
        for (int j = i + 1; j <= n; j++)
            if (checked[dsu_parent (j)] == 0)   
                v.push_back (j);
        int n = v.size() - 1;

        queue <pair <int, int> > q;
        q.push ({0, n});

        while (!q.empty()) {
            int L = q.back().first, R = q.back().second;
            q.pop();

            if (L == R)
                chk (v, L, R, i);
            else {
                pair <int, int> ret1 = chk (v, L, (L + R) / 2, i);
                pair <int, int> ret2 = chk (v, (L + R) / 2 + 1, R, i);

                if (ret1.first != -1)
                    q.push (ret1);
                if (ret2.first != -1)
                    q.push (ret2);
            }
        }

        checked[i] = 1;
    }

    cout << 0 << ' ';
    for (int i = 1; i <= n; i++)
        cout << dsu_parent (i) << ' ';
    cout.flush();
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 432 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 24 ms 428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -