Submission #1257607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257607		nerrrmin	Sphinx's Riddle (IOI24_sphinx)	C++20	28.50 / 100	28 ms	1180 KiB

sphinx

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

int same[maxn];

vector < int > g[maxn];
int used[maxn], a[maxn];
void dfs(int beg)
{
    used[beg] = 1;
    for (auto nb: g[beg])
    {
        if(used[nb])continue;
        if(a[nb] != n)continue;
        dfs(nb);
    }
}
int col[maxn];

int dp[maxn];

int ask(int mid, int curr)
{
    vector < int > g;
    int is = 0;
    for (int i = 0; i < n; ++ i)
    {
        if(i <= mid)g.pb(-1);
        else if(i == curr)g.pb(-1);
        else
        {
            is = 1;
            g.pb(n);
        }
    }


    int ans = perform_experiment(g);

    return ans-is;
}
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 < m; ++ i)
    {
        g[X[i]].pb(Y[i]);
        g[Y[i]].pb(X[i]);
    }

    dp[0] = 1;
    col[0] = 0;
    int mx = 0;
    for (int i = 1; i < n; ++ i)
    {

       // vector < int >
        int l = 0, r = i-1, mid, ans = i; /// pyrvoto obyrkano
        while(l <= r)
        {
            mid = (l + r)/2;
            int fb = ask(mid, i);
            if(fb == dp[mid])
            {
                r = mid - 1;
                ans = mid;
            }
            else
            {
                l = mid+1;
            }
        }

       // cout << ans << endl;
        if(ans == i)
        {
            mx ++;
            dp[i] = dp[i-1] + 1;
            col[i] = mx;
        }
        else
        {
            dp[i] = dp[i-1];
            col[i] = col[ans];
        }
       // cout << "dp is " << i << " " << dp[i] << endl;
    }

    vector < int > res;
    for (int i = 0; i < n; ++ i)
        res.pb(col[i]);
    return res;
    /*std::vector<int> e(N, -1);

    for (int i = 0; i < n-1; ++ i)
    {
        vector < int > g;
        int pre = 0, post = 0;
        for (int j = 0; j < i; ++ j)
        {
            g.pb(n);
            pre = 1;
        }
        g.pb(-1);
        g.pb(-1);
        for (int j = i+2; j < n; ++ j)
        {
            g.pb(n);
            post = 1;
        }
        int fb = perform_experiment(g);
        if(fb == pre + post + 1)same[i+1] = 1;
        else same[i+1] = 0;
    }

   // vector< int > res;
    res.pb(0);
    int curr = 0;
    for (int i = 1; i < n; ++ i)
    {
        if(same[i])res.pb(curr);
        else
        {
            curr ++;
            res.pb(curr);
        }
    }
*/
    return res;
}

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