Submission #710270

#	Time	Username	Problem	Language	Result	Execution time	Memory
710270		vjudge1	Carnival (CEOI14_carnival)	C++17	100 / 100	16 ms	328 KiB

carnival

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20