Submission #1235034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235034		HossamHero7	Sphinx's Riddle (IOI24_sphinx)	C++20	0 / 100	1 ms	320 KiB

sphinx

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#include "sphinx.h"
// #include "grader.cpp"
bool vis[505];
vector<int> g[505];
vector<int> color;
int CC;
int n;
vector<int> p;
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
    n = N;
    color.resize(n);
    vector<int> v{0};
    auto query = [&](int l,int r,int x){
        int a,b;
        cin>>a>>b;
        vector<int> tmp(n,n);
        for(int i=l;i<=r;i++) tmp[v[i]] = -1;
        tmp[x] = -1;
        bool rem = n - (r - l + 1) - 1;
        return perform_experiment(tmp) == r - l + 2 + rem;
    };
    int pt = 1;
    for(int i=1;i<n;i++){
        int l = 0;
        int r = (int)v.size() - 1;
        if(query(0,(int)v.size()-1,i)){
            v.push_back(i);
            color[i] = pt ++;
            continue;
        }
        while(l < r){
            int md = (l + r) >> 1;
            if(query(l,md,i)){
                l = md + 1;
            }
            else r = md;
        }
        color[i] = color[v[l]];
    }
    vector<int> id(pt,n-1);
    for(int c=0;c<n-1;c++){
        int l = 0;
        int r = v.size();
        r --;
        if(l == r){
            vector<int> tmp(n,c);
            tmp[v[0]] = -1;
            if(perform_experiment(tmp) != 1) r = -1;
        }
        bool b = 0;
        while(l < r){
            int md = (l + r) >> 1;
            vector<int> tmp(n,c);
            for(int i=l;i<=md;i++) tmp[v[i]] = -1;
            if(perform_experiment(tmp) == md - l + 1){
                r = md;
            }
            else {
                if(b){
                    l = md + 1;
                }
                else {
                    fill(tmp.begin(),tmp.end(),c);
                    for(int i=md+1;i<=r;i++) tmp[v[i]] = -1;
                    if(perform_experiment(tmp) == r - (md+1) + 1){
                        l = md + 1;
                    }
                    else goto gt;
                }
            }
            b - 1;
        }
        if(l == r) {
            id[color[v[l]]] = c;
            v.erase(v.begin()+l);
            if(v.empty()) break;
        }
        gt:continue;
    }
    for(auto &i:color) i = id[i];
    return color;
}

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