Submission #1239378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239378		inesfi	Sphinx's Riddle (IOI24_sphinx)	C++20	36 / 100	33 ms	440 KiB

sphinx

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

// int x = perform_experiment(E);

vector<int> mur;
vector<int> rep;
int n;

int calc_compo(vector<pair<int,int>> v){
    int nbc=v.size()*3-1;
    if (v[0].first!=0 and v[0].second!=0){
        nbc++;
    }
    if (v.back().first!=n-1 and v.back().second!=n-1){
        nbc++;
    }
    return nbc;
}

void trouver(vector<pair<int,int>> candidats_voisins){
    int couleur=0;
    while (couleur<n-1 and !candidats_voisins.empty()){
        //cout<<42<<endl;
        /*for (auto i:candidats_voisins){
            cout<<i.first<<" "<<i.second<<endl;
        }*/
        vector<int> quest=mur;
        for (auto c:candidats_voisins){
            quest[c.first]=-1; // la case de la question
            quest[c.second]=couleur; // la case voisine pour la question 
        }
        int nbcompo=calc_compo(candidats_voisins);
        //cout<<nbcompo<<endl;
        int vrai_nbcompo=perform_experiment(quest);
        /*cout<<vrai_nbcompo<<endl;
        for (int i:quest){
            cout<<i<<" ";
        }
        cout<<endl;*/
        if (vrai_nbcompo==nbcompo){
            couleur++;
            //cout<<42<<endl;
        }
        else {
            //cout<<42<<endl;
            int g=0,d=candidats_voisins.size()-1;
            while (g<d){
                int mil=(g+d+1)/2;
                vector<int> nouv=mur;
                vector<pair<int,int>> nouv_candidats={};
                for (int i=g;i<mil;i++){
                    nouv[candidats_voisins[i].first]=-1;
                    nouv[candidats_voisins[i].second]=couleur;
                    nouv_candidats.push_back(candidats_voisins[i]);
                }
                int nbcompo=calc_compo(nouv_candidats);
                int vrai_nbcompo=perform_experiment(nouv);
                if (vrai_nbcompo==nbcompo){
                    g=mil;
                }
                else {
                    d=mil-1;
                }
            }
            rep[candidats_voisins[g].first]=couleur;
            vector<pair<int,int>> nouv_candidats={};
            for (int i=0;i<(int)candidats_voisins.size();i++){
                if (i!=g){
                    nouv_candidats.push_back(candidats_voisins[i]);
                }
            }
            candidats_voisins=nouv_candidats;
        }
    }
    for (auto c:candidats_voisins){
        rep[c.first]=n-1;
    }
}

vector<int> find_colours(int N,vector<int> deb,vector<int> fin) {
    n=N;
    for (int i=0;i<n;i++){
        mur.push_back(n);
        rep.push_back(n);
    }
    vector<pair<int,int>> quest={};
    for (int i=0;i<n-1;i+=3){
        quest.push_back({i,i+1});
    }
    trouver(quest);
    //return {0};
    //cout<<42<<endl;
    //return {0};
    quest={};
    for (int i=1;i<n;i+=3){
        quest.push_back({i,i-1});
    }
    trouver(quest);
    quest={};
    for (int i=2;i<n;i+=3){
        quest.push_back({i,i-1});
    }
    trouver(quest);
    quest={};
    if (n%3==1){
        trouver({{n-1,n-2}});
    }
    return rep;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 0 / 7
• Subtask 3: 33 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36