Submission #1202413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202413		Pacybwoah	Sphinx's Riddle (IOI24_sphinx)	C++20	36 / 100	34 ms	412 KiB

sphinx

#include "sphinx.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
std::vector<int> find_colours(int n, std::vector<int> X, std::vector<int> Y){
    int m = (int)X.size();
    vector<vector<int>> graph(n);
    for(int i = 0; i < m; i++){
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }
    vector<int> que(n), ans(n, -1), imp;
    for(int i = 2; i < n; i += 2) imp.push_back(i);
    for(int col = 0; col < n; col++){
        fill(que.begin(), que.end(), -1);
        for(int i = 1; i < n; i += 2) que[i] = col;
        que[0] = n;
        int res = perform_experiment(que);
        if(res == n) continue;
        res = n - res;
        if(res & 1){
            ans[n - 1] = col;
            res--;
        }
        res /= 2;
        int lst = 0;
        int sz = (int)imp.size();
        for(int times = 0; times < res; times++){
            int l = lst, r = sz - 1;
            while(l < r){
                int mid = (l + r) >> 1;
                for(int i = 0; i <= mid; i++){
                    que[imp[i]] = n;
                }
                for(int i = mid + 1; i < sz; i++){
                    que[imp[i]] = -1;
                }
                int ress = perform_experiment(que);
                ress = (n - ress) / 2;
                if(ress == res - times) l = mid + 1;
                else r = mid;
            }
            ans[imp[l]] = col;
            lst = l + 1;
        }
    }
    vector<int>().swap(imp);
    for(int i = 1; i < n; i += 2) imp.push_back(i);
    for(int col = 0; col < n; col++){
        fill(que.begin(), que.end(), -1);
        for(int i = 0; i < n; i += 2) que[i] = col;
        int res = perform_experiment(que);
        if(res == n) continue;
        res = n - res;
        if(res & 1){
            ans[n - 1] = col;
            res--;
        }
        res /= 2;
        int lst = 0;
        int sz = (int)imp.size();
        for(int times = 0; times < res; times++){
            int l = lst, r = sz - 1;
            while(l < r){
                int mid = (l + r) >> 1;
                for(int i = 0; i <= mid; i++){
                    que[imp[i]] = n;
                }
                for(int i = mid + 1; i < sz; i++){
                    que[imp[i]] = -1;
                }
                int ress = perform_experiment(que);
                ress = (n - ress) / 2;
                if(ress == res - times) l = mid + 1;
                else r = mid;
                //cout << col << " " << mid << " " << ress << " " << res - times << endl;
            }
            ans[imp[l]] = col;
            lst = l + 1;
        }
    }
    for(int col = 0; col < n; col++){
        fill(que.begin(), que.end(), col);
        que[0] = -1;
        if(perform_experiment(que) == 1){
            ans[0] = col;
            break;
        }
    }
    return ans;
}

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