Submission #1252381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252381		rayan_bd	Carnival (CEOI14_carnival)	C++20	100 / 100	12 ms	420 KiB

carnival

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

vector<int> adj[155];
int vis[155], tin = 1;
//vector<int> ar = {1, 1, 2, 3, 4, 5, 6, 7, 7, 10};

void dfs(int u){
    vis[u] = tin;  
    for(auto it : adj[u]){
        if(vis[it] == -1){
            dfs(it);
        }
    }
}

int main(){
    int n;
    cin >> n;

    //n = ar.size();

    auto ask = [&](int i, int j){
        if(i > j) return -1;
        if(i == j) return 1;
        int res = 0;
        cout << j - i + 1 << " ";
       // set<int> st;
        while(i <= j){
           // st.insert(ar[i - 1]);
            cout << i << " ";
            i += 1;
        }
        cout << endl << "\n";
        //res = st.size();
        cin >> res;
        return res;
    };
    
    memset(vis, -1, sizeof(vis));
    
    for(int i = 1; i <= n; ++i){
        int st = i, en = n, nxt = -1;
        while(st <= en){
            int mid = st + (en - st) / 2;
            int tp1 = ask(i + 1, mid);
            int tp2 = ask(i, mid);
            if(tp1 == tp2){
                nxt = mid;
                en = mid - 1;
            }else{
                st = mid + 1;
            }
        }
       // if(i == 8) cout << "next:- " << nxt << endl;
        if(nxt > 0) adj[i].push_back(nxt), adj[nxt].push_back(i);
    }

    for(int i = 1; i <= n; ++i){
        if(vis[i] == -1){
            dfs(i);
            tin += 1;
        }
    }

    cout << "0 ";
    for(int i = 1; i <= n; ++i) cout << vis[i] << " ";

    return 0;
}

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