제출 #1180801

#제출 시각아이디문제언어결과실행 시간메모리
1180801kilikumaCarnival (CEOI14_carnival)C++20
0 / 100
0 ms420 KiB
#include <bits/stdc++.h>
using namespace std;

int N, P[151];

int F(int u) {
    while (P[u] != u) P[u] = P[P[u]], u = P[u];
    return u;
}

void U(int u, int v) {
    int a = F(u), b = F(v);
    if (a != b) P[b] = a;
}

void find_matching_group(int x, vector<int>& groups) {
    int l = 0, r = groups.size();
    while (l < r) {
        int m = (l + r) / 2;
        cout << m+1 << ' ';
        for (int i = 0; i <= m; i++) cout << groups[i] << ' ';
        cout << x << endl;
        int R; cin >> R;
        if (R <= m+1) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    if (l < groups.size()) {
        cout << "2 " << groups[l] << ' ' << x << endl;
        int R; cin >> R;
        if (R == 1) U(groups[l], x);
    }
}

void D(vector<int> f) {
    if (f.size() == 1) return;
    int m = f.size() / 2;
    vector<int> l(f.begin(), f.begin() + m), r(f.begin() + m, f.end());
    D(l), D(r);
    
    map<int, vector<int>> group_map;
    for (int x : l) group_map[F(x)].push_back(x);
    
    for (int x : r) {
        if (group_map.empty()) break;
        vector<int> group_reps;
        for (auto& [k, v] : group_map) group_reps.push_back(v[0]);
        
        find_matching_group(x, group_reps);
    }
}

int main() {
    cin >> N;
    for (int i = 1; i <= N; ++i) P[i] = i;
    vector<int> f(N); iota(f.begin(), f.end(), 1);
    D(f);
    map<int, int> m; int c = 0;
    cout << "0 ";
    for (int i = 1; i <= N; ++i) {
        int r = F(i);
        if (!m.count(r)) m[r] = ++c;
        cout << m[r] << ' ';
    }
    cout << endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...