제출 #1257810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257810		nerrrmin	Sphinx's Riddle (IOI24_sphinx)	C++20	0 / 100	0 ms	412 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();
    memset(a, -1, sizeof(a));
    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)
    {
        if(even.size() == 0)break;
        int pre = -1;

               if(ask_even(-1, n, c) == n)
               {
                   continue;
               }

       // 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;
            }
        }
        even.clear();
        for (int j = 0; j < n; ++ j)
        {
            if(j % 2 == 0)
            {
                if(a[j] == -1)even.pb(j);
            }
        }
    }
    for (int c = 0; c < n; ++ c)
    {
        if(odd.size() == 0)break;
        int v = ask_odd(-1, n, c);
        int cnt = (n - v)/2;
    if(v == n)
            {
                   continue;
            }
        int pre = -1;
        int sz = odd.size();
        while(cnt --)
        {
            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;
            }
        }
        odd.clear();
        for (int j = 0; j < n; ++ j)
        {
            if(j & 1)
            {
                if(a[j] == -1)odd.pb(j);
            }
        }
    }

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

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