Submission #1187783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187783		inesfi	Carnival (CEOI14_carnival)	C++20	100 / 100	6 ms	476 KiB

carnival

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

#define int long long

const int TAILLEMAXI=152;
vector<int> adja[TAILLEMAXI];
int dejavu[TAILLEMAXI];
vector<int> reste;
int tour;

void dfs(int a){
    if (dejavu[a]!=0){
        return ;
    }
    dejavu[a]=tour;
    for (int i:adja[a]){
        dfs(i);
    }
}

bool dedans(vector<int> v,int a){
    if (v.size()==1){
        cout<<2<<" "<<v[0]+1<<" "<<a+1<<endl;
        int val;
        cin>>val;
        if (val==2){
            return false;
        }
        return true;
    }
    cout<<v.size()<<" ";
    for (int i:v){
        cout<<i+1<<" ";
    }
    cout<<endl;
    int val1;
    cin>>val1;
    cout<<v.size()+1<<" ";
    for (int i:v){
        cout<<i+1<<" ";
    }
    cout<<a+1<<endl;
    int val2;
    cin>>val2;
    if (val1==val2){
        return true;
    }
    return false;
}

void trouver(vector<int> v,int a){
    if (v.size()==1){
        //cout<<"adja"<<v[0]+1<<" "<<a+1<<endl;
        adja[v[0]].push_back(a);
        adja[a].push_back(v[0]);
        return ;
    }
    vector<int> moitie;
    moitie.clear();
    for (int i=0;i<(int)v.size()/2;i++){
        moitie.push_back(v[i]);
    }
    //cout<<"quest "<<a+1<<" "<<moitie.size()<<endl;
    if (dedans(moitie,a)){
        trouver(moitie,a);
    }
    else {
        vector<int> autre;
        autre.clear();
        for (int i=(int)moitie.size();i<(int)v.size();i++){
            autre.push_back(v[i]);
        }
        trouver(autre,a);
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int nbpers;
    cin>>nbpers;
    for (int i=0;i<nbpers;i++){
        reste.push_back(i);
    }
    for (int i=nbpers-1;i>=1;i--){
        reste.pop_back();
        if (dedans(reste,i)){
            //cout<<"OUI"<<endl;
            trouver(reste,i);
        }
        else {
            //cout<<"NON"<<endl;
        }
    }
    cout<<0<<" ";
    for (int i=0;i<nbpers;i++){
        if (dejavu[i]==0){
            tour++;
            dfs(i);
        }
        cout<<dejavu[i]<<" ";
    }
    cout<<endl;
    return 0;
}

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