Submission #1192233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192233		NotLinux	Sphinx's Riddle (IOI24_sphinx)	C++20	36 / 100	37 ms	560 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 <= 0){
        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 if(sz(x) == n * (n-1) / 2){
        // 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;
            }
        }
        map<pair<int,int>,int>mpa;
        auto getran = [&](int l , int r , int renk){
            vector<int>vec(n,n);
            for(int i = l;i<=r;i++){
                vec[i] = -1;
            }
            int res1;
            if(mpa[{l,r}])res1 = mpa[{l,r}];
            else{
                res1 = perform_experiment(vec);
                mpa[{l,r}] = res1;
            }
            for(int i = 0;i<n;i++)if(vec[i] == n)vec[i] = renk;
            int res2 = perform_experiment(vec);
            // cout << "getran : " << l << " " << r << " " << renk << " : " << res1 - res2 << endl;
            return res1 - res2;
        };
        function<void(int,int,int)> dfs = [&](int l , int r , int renk){// bu rangede bu renkten varmi
            int res1 = getran(l,r,renk);
            if(res1 == 0)return;
            if(l != r){
                int mid = (l + r) / 2;
                int res2 = getran(l,mid,renk);
                if(res2)dfs(l,mid,renk);
                if(res1 - res2)dfs(mid+1,r,renk);
            }
            else{
                col[l] = renk;
            }
        };
        for(int i = 0;i<n;i++){
            dfs(1,n-1,i);
        }
    }
    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: 0 / 7
• Subtask 3: 33 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36