Submission #292251

#	Time	Username	Problem	Language	Result	Execution time	Memory
292251		davooddkareshki	Carnival (CEOI14_carnival)	C++17	100 / 100	24 ms	384 KiB

carnival

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

typedef long long ll;

const int maxn = 155;
const int mod = 1e9+7;

int n, m, k;
struct dsu
{
    int par[maxn];
    dsu() {memset(par, -1, sizeof par);}
    int get_par(int v) {if(par[v] == -1) return v; return par[v] = get_par(par[v]);}
    void merg(int u, int v)
    {
        if(u == -1 || v == -1) return;
        u = get_par(u);
        v = get_par(v);
        if(u == v) return;
        par[u] = v;
    }
} dsu;

bool ask(vector<int> ve)
{
    cout<< ve.size() <<" ";
    for(auto x : ve) cout<< x <<" "; cout<< endl;
    int x; cin>> x;
    return (x < (int)ve.size());
}

pii find_edge(vector<int> ve)
{
    int lo = 0, hi = (ve.size())-1;
    if(ask(ve) == 0) return {-1,-1};
    while(hi-lo > 1)
    {
        int tm = (hi + lo) >> 1;
        vector<int> vec;
        for(int i = 0; i <= tm; i++)
            vec.push_back(ve[i]);
        if(ask(vec)) hi = tm;
        else lo = tm;
    }

    int v = ve[hi];
    lo = -1, hi = hi-1;
    while(hi-lo > 1)
    {
        int tm = (hi + lo) >> 1;
        vector<int> vec;
        vec.push_back(v);
        for(int i = 0; i <= tm; i++)
            vec.push_back(ve[i]);
        if(ask(vec)) hi = tm;
        else lo = tm;
    }
    return {v,ve[hi]};
}

signed main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>> n;

    for(int I = 1; I < n; I++)
    {
        vector<int> ve;
        for(int i = 1; i <= n; i++)
            if(dsu.par[i] == -1) ve.push_back(i);
        pii e = find_edge(ve);
        dsu.merg(e.F,e.S);
    }

    int lst = 0;
    int X[maxn];
    for(int i = 1; i <= n; i++)
        if(dsu.par[i] == -1) X[i] = ++lst;

    cout<< 0 <<" ";
    for(int i = 1; i <= n; i++)
        cout<< X[dsu.get_par(i)] <<" ";
}
/*
10 15
1 3
5 1
2 3
9 2
3 4
6 3
4 5
7 4
4 8
5 7
8 5
6 7
7 8
8 10
10 9
*/

Compilation message (stderr)

carnival.cpp: In function 'bool ask(std::vector<long long int>)':
carnival.cpp:34:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   34 |     for(auto x : ve) cout<< x <<" "; cout<< endl;
      |     ^~~
carnival.cpp:34:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   34 |     for(auto x : ve) cout<< x <<" "; cout<< endl;
      |                                      ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20