oj.uz

Submission #292251

# Submission time Handle Problem Language Result Execution time Memory
292251 2020-09-06T15:41:36 Z davooddkareshki Carnival (CEOI14_carnival) C++17
100 / 100
 24 ms 384 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 384 KB Output is correct
2 Correct 20 ms 256 KB Output is correct
3 Correct 13 ms 376 KB Output is correct
4 Correct 6 ms 256 KB Output is correct
5 Correct 8 ms 384 KB Output is correct
6 Correct 16 ms 256 KB Output is correct
7 Correct 10 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 256 KB Output is correct
2 Correct 24 ms 256 KB Output is correct
3 Correct 10 ms 256 KB Output is correct
4 Correct 8 ms 384 KB Output is correct
5 Correct 15 ms 256 KB Output is correct
6 Correct 19 ms 256 KB Output is correct
7 Correct 17 ms 256 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 256 KB Output is correct
2 Correct 15 ms 384 KB Output is correct
3 Correct 20 ms 256 KB Output is correct
4 Correct 6 ms 256 KB Output is correct
5 Correct 16 ms 256 KB Output is correct
6 Correct 21 ms 256 KB Output is correct
7 Correct 21 ms 256 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 256 KB Output is correct
2 Correct 16 ms 256 KB Output is correct
3 Correct 10 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 16 ms 256 KB Output is correct
6 Correct 14 ms 256 KB Output is correct
7 Correct 24 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 384 KB Output is correct
2 Correct 23 ms 256 KB Output is correct
3 Correct 18 ms 256 KB Output is correct
4 Correct 13 ms 256 KB Output is correct
5 Correct 17 ms 256 KB Output is correct
6 Correct 10 ms 384 KB Output is correct
7 Correct 8 ms 256 KB Output is correct