Submission #1257799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257799		nerrrmin	Sphinx's Riddle (IOI24_sphinx)	C++20	3 / 100	38 ms	440 KiB

sphinx

#include "sphinx.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 255;
int n, m;
int a[maxn];
vector < int > even, odd;

int ask_even(int st, int fi, int c)
{
    //cout << "ask " << endl;
    vector < int > g(n, 0);
    for (int i = 0; i < n; ++ i)
    {
        if(i & 1)g[i] = c;
        else if(i < st || i > fi)g[i] = n;
        else g[i] = -1;
    }
    int fb = perform_experiment(g);
    return fb;
}
int ask_odd(int st, int fi, int c)
{
    //cout << "ask 2 " << endl;
    vector < int > g(n, 0);
    for (int i = 0; i < n; ++ i)
    {
        if(i % 2 == 0)g[i] = c;
        else if(i < st || i > fi)g[i] = n;
        else g[i] = -1;
    }
    int fb = perform_experiment(g);
    return fb;
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y)
{
    n = N;
    m = X.size();

    for (int i = 0; i < n; ++ i)
    {
        if(i % 2 == 0)even.pb(i);
        else odd.pb(i);
    }

    for (int c = 0; c < n; ++ c)
    {
        int pre = -1;

       // cout << pre << " " << even.size() << endl;
        int sz = even.size();
        while(pre < sz)
        {
         //   cout << "ehere " << endl;
            int l = pre+1, r = sz-1, mid, ans = sz; /// pyrvoto koeto naebava
            while(l <= r)
            {
                mid = (l + r)/2;
                if(ask_even(even[pre+1], even[mid], c) == n)
                {
                    l = mid + 1;
                }
                else
                {
                    r = mid - 1;
                    ans = mid;
                }
            }
            pre = ans;
            if(ans < even.size())
            {
                int pos = even[ans];
                a[pos] = c;
            }
        }
    }
    for (int c = 0; c < n; ++ c)
    {
        int pre = -1;
        int sz = odd.size();
        while(pre < sz)
        {
            int l = pre+1, r = sz-1, mid, ans = sz; /// pyrvoto koeto naebava
            while(l <= r)
            {
                mid = (l + r)/2;
                if(ask_odd(odd[pre+1], odd[mid], c) == n)
                {
                    l = mid + 1;
                }
                else
                {
                    r = mid - 1;
                    ans = mid;
                }
            }
            pre = ans;
            if(ans < odd.size())
            {
                int pos = odd[ans];
                a[pos] = c;
            }
        }
    }

    vector < int > res;
    for (int i = 0 ;i < n; ++ i)
        res.pb(a[i]);
    return res;
}

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