Submission #1257583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257583		nerrrmin	Sphinx's Riddle (IOI24_sphinx)	C++20	10 / 100	164 ms	1188 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];
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]);
    }


    for (int i = 0; i < n; ++ i)
    {
        for (int c = 0; c < n; ++ c)
        {
            int other = g[i][0];
            vector < int > g;
            for (int j = 0; j < n; ++ j)
            {
                if(j == i)g.pb(-1);
                else if(j == other)g.pb(c);
                else g.pb(n);
            }
            for (int j = 0; j < n; ++ j)
                a[j] = g[j];
            int fb = perform_experiment(g);
            int cnt  = 0;
            for (int j = 0; j < n; ++ j)
                used[j] = 0;
            for (int j = 0; j < n; ++ j)
            {
                if(used[j])continue;
                if(a[j] != n)continue;
                cnt ++;
                dfs(j);
            }
            if(fb == cnt + 1)
            {
                col[i] = c;
                break;
            }
        }
    }

    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: 3 / 3
• Subtask 2: 7 / 7
• Subtask 3: 0 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36