제출 #1192229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192229		NotLinux	Sphinx's Riddle (IOI24_sphinx)	C++20	43 / 100	40 ms	1024 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
vector<int> find_colours(int n, vector<int> x, vector<int> y) {
    vector<int>col(n);
    if(n <= 50){
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                vector<int>vec(n,j);
                vec[i] = -1;
                if(perform_experiment(vec) == 1){
                    col[i] = j;
                    break;
                }
            }
        }
    }
    else{
        // ilkinin rengini bul
        for(int j = 0;j<n;j++){
            vector<int>vec(n,j);
            vec[0] = -1;
            if(perform_experiment(vec) == 1){
                col[0] = j;
                break;
            }
        }
        // sonuncunun rengini bul
        for(int j = 0;j<n;j++){
            vector<int>vec(n,j);
            vec[n-1] = -1;
            if(perform_experiment(vec) == 1){
                col[n-1] = j;
                break;
            }
        }
        map<array<int,4>,int>mpa;
        auto getran = [&](int l , int r , int renk , int odd){// l r araliginda tek/ciftlerde kac tane renk var
            if(l == r and (l&1) != (odd&1))return 0;
            else if(mpa.count({l,r,renk,odd}))return mpa[{l,r,renk,odd}];
            vector<int>vec(n,renk);
            int saymaca = 0;
            for(int i = l;i<=r;i++){
                if((i&1) == (odd&1)){
                    vec[i] = -1;
                    saymaca++;
                }
            }
            int ret = saymaca - (perform_experiment(vec) - 1) / 2;
            mpa[{l,r,renk,odd}] = ret;
            return ret;
        };
        for(int i = 0;i<2;i++){
            for(int j = 0;j<n;j++){
                int sayac = 0 , lst = 0;
                while(sayac < getran(1,n-2,j,i)){
                    int l = lst+1 , r = n-2;
                    while(l < r){
                        int mid = (l + r) / 2;
                        if(getran(l,mid,j,i))r = mid;
                        else l = mid+1;
                    }
                    col[l] = j;
                    sayac++;
                    lst = l;
                }
            }
        }
    }
    return col;
}

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