oj.uz

답안 #710269

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
710269 2023-03-15T06:26:38 Z minhnhatnoe 사육제 (CEOI14_carnival) C++14
100 / 100
 18 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int query(const vector<int> &c){
    if (c.size() <= 1) return c.size();
    cout << c.size() << "\n";
    for (int i=0; i<c.size(); i++){
        cout << c[i]+1 << " \n"[i == c.size()-1];
    }
    cout << flush;
    int val; cin >> val;
    return val;
}
struct dsu{
    vector<int> p;
    dsu(int n): p(n, -1) {}
    int find(int v){
        if (p[v] < 0) return v;
        return p[v] = find(p[v]);
    }
    void merge(int a, int b){
        a = find(a), b = find(b);
        if (a == b) return;
        if (-p[a] < -p[b]) swap(a, b);
        p[a] += p[b];
        p[b] = a;
    }
    vector<int> get_heads(){
        vector<int> a;
        for (int i=0; i<p.size(); i++){
            if (p[i] < 0) a.push_back(i);
        }
        return a;
    }
};
pair<int, int> search_edge(const vector<int> &a, const vector<int> &b){
    if (a.size() == 1 && b.size() == 1) return {a[0], b[0]};
    if (a.size() == 1) return search_edge(b, a);
    vector<int> x(a.begin(), a.begin() + a.size()/2);
    x.insert(x.end(), b.begin(), b.end());
    if (query(x) != x.size())
        return search_edge(vector<int> (a.begin(), a.begin() + a.size()/2), b);
    else
        return search_edge(vector<int> (a.begin() + a.size()/2, a.end()), b);
}
pair<int, int> search_edge(const vector<int> &s){
    if (s.size() == 2) return {s[0], s[1]};
    vector<int> a(s.begin(), s.begin() + s.size()/2);
    vector<int> b(s.begin() + s.size()/2, s.end());
    if (query(a) != a.size())
        return search_edge(a);
    if (query(b) != b.size())
        return search_edge(b);
    return search_edge(a, b);
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    dsu g(n);
    while (true){
        vector<int> c = g.get_heads();
        if (query(c) == c.size()) break;
        pair<int, int> e = search_edge(c);
        g.merge(e.first, e.second);
    }
    vector<int> a(n, -1);
    int c = 0;
    for (int i=0; i<n; i++){
        if (g.find(i) == i) a[i] = c++;
    }
    cout << "0\n";
    for (int i=0; i<n; i++){
        cout << a[g.find(i)]+1 << " \n"[i == n-1];
    }
}

Compilation message

carnival.cpp: In function 'int query(const std::vector<int>&)':
carnival.cpp:7:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i=0; i<c.size(); i++){
      |                   ~^~~~~~~~~
carnival.cpp:8:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |         cout << c[i]+1 << " \n"[i == c.size()-1];
      |                                 ~~^~~~~~~~~~~~~
carnival.cpp: In member function 'std::vector<int> dsu::get_heads()':
carnival.cpp:30:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int i=0; i<p.size(); i++){
      |                       ~^~~~~~~~~
carnival.cpp: In function 'std::pair<int, int> search_edge(const std::vector<int>&, const std::vector<int>&)':
carnival.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     if (query(x) != x.size())
      |         ~~~~~~~~~^~~~~~~~~~~
carnival.cpp: In function 'std::pair<int, int> search_edge(const std::vector<int>&)':
carnival.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     if (query(a) != a.size())
      |         ~~~~~~~~~^~~~~~~~~~~
carnival.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     if (query(b) != b.size())
      |         ~~~~~~~~~^~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         if (query(c) == c.size()) break;
      |             ~~~~~~~~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 208 KB Output is correct
2 Correct 13 ms 208 KB Output is correct
3 Correct 6 ms 208 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 9 ms 208 KB Output is correct
6 Correct 12 ms 208 KB Output is correct
7 Correct 12 ms 208 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 208 KB Output is correct
2 Correct 8 ms 320 KB Output is correct
3 Correct 5 ms 208 KB Output is correct
4 Correct 3 ms 320 KB Output is correct
5 Correct 13 ms 208 KB Output is correct
6 Correct 10 ms 208 KB Output is correct
7 Correct 12 ms 320 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 208 KB Output is correct
2 Correct 12 ms 316 KB Output is correct
3 Correct 11 ms 208 KB Output is correct
4 Correct 2 ms 208 KB Output is correct
5 Correct 9 ms 316 KB Output is correct
6 Correct 10 ms 320 KB Output is correct
7 Correct 11 ms 320 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 208 KB Output is correct
2 Correct 12 ms 324 KB Output is correct
3 Correct 5 ms 324 KB Output is correct
4 Correct 2 ms 208 KB Output is correct
5 Correct 13 ms 320 KB Output is correct
6 Correct 9 ms 328 KB Output is correct
7 Correct 13 ms 208 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 208 KB Output is correct
2 Correct 18 ms 316 KB Output is correct
3 Correct 6 ms 328 KB Output is correct
4 Correct 9 ms 332 KB Output is correct
5 Correct 8 ms 208 KB Output is correct
6 Correct 6 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct