Submission #1229249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229249		PVM_pvm	Sphinx's Riddle (IOI24_sphinx)	C++20	36 / 100	38 ms	436 KiB

sphinx

#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 252
int find_ch(int le, int re, int col)
{
    int N=re+1;
    if (le>re) return -1;
    if (le==re && le%2==1) return -1;
    if (le==re)
    {
        vector<int> E(N, N);
        E[le]=-1;
        E[le-1]=col;
        int xx=perform_experiment(E);
        if (N==2)
        {
            if (xx==2) return -1;
            else return le;
        }
        else
        {
            if (xx==3) return -1;
            else return le;
        }
    }
    vector<int> E(N);
    int ochr=re-le+1;
    if (le!=0) ochr++;
    for (int q=0;q<le;q++) E[q]=N;
    for (int q=le;q<=re;q++)
    {
        if (q%2==0) E[q]=-1;
        else E[q]=col;
    }
    int xx=perform_experiment(E);
    if (xx==ochr) return -1;
    int l=le-1,r=re;
    while (l<r-1)
    {
        int mid=(l+r)/2;
        if (mid==le)
        {
            for (int q=0;q<le;q++) E[q]=N;
            for (int q=le;q<=mid+1;q++)
            {
                if (q%2==0) E[q]=-1;
                else E[q]=col;
            }
            for (int q=mid+2;q<N;q++)
            {
                E[q]=N;
            }
            int ochr=mid+1-le+1;
            if (le!=0) ochr++;
            if (mid!=(N-2)) ochr++;
            xx=perform_experiment(E);
            //cout<<xx<<" "<<ochr<<"\n";
            if (xx==ochr) l=mid;
            else r=mid;
            continue;
        }
        ochr=mid-le+1;
        if (mid!=N-1) ochr++;
        if (le!=0) ochr++;
        for (int q=0;q<le;q++) E[q]=N;
        for (int q=le;q<=mid;q++)
        {
            if (q%2==0) E[q]=-1;
            else E[q]=col;
        }
        for (int q=mid+1;q<N;q++)
        {
            E[q]=N;
        }
        xx=perform_experiment(E);
        //cout<<xx<<" "<<ochr<<"\n";
        if (xx==ochr) l=mid;
        else r=mid;
    }
    return r;
}
int find_nc(int le, int re, int col)
{
    int N=re+1;
    if (le>re) return -1;
    if (le==re && le%2==0) return -1;
    if (le==re)
    {
        vector<int> E(N, N);
        E[le]=-1;
        E[le-1]=col;
        int xx=perform_experiment(E);
        if (N==2)
        {
            if (xx==2) return -1;
            else return le;
        }
        else
        {
            if (xx==3) return -1;
            else return le;
        }
    }
    vector<int> E(N);
    int ochr=re-le+1;
    if (le!=0) ochr++;
    for (int q=0;q<le;q++) E[q]=N;
    for (int q=le;q<=re;q++)
    {
        if (q%2==1) E[q]=-1;
        else E[q]=col;
    }
    int xx=perform_experiment(E);
    if (xx==ochr) return -1;
    int l=le-1,r=re;
    while (l<r-1)
    {
        int mid=(l+r)/2;
        ochr=mid-le+1;
        if (mid==le)
        {
            for (int q=0;q<le;q++) E[q]=N;
            for (int q=le;q<=mid+1;q++)
            {
                if (q%2==1) E[q]=-1;
                else E[q]=col;
            }
            for (int q=mid+2;q<N;q++)
            {
                E[q]=N;
            }
            int ochr=mid+1-le+1;
            if (le!=0) ochr++;
            if (mid!=(N-2)) ochr++;
            xx=perform_experiment(E);
            //cout<<xx<<" "<<ochr<<"\n";
            if (xx==ochr) l=mid;
            else r=mid;
            continue;
        }
        if (mid!=N-1) ochr++;
        if (le!=0) ochr++;
        for (int q=0;q<le;q++) E[q]=N;
        for (int q=le;q<=mid;q++)
        {
            if (q%2==1) E[q]=-1;
            else E[q]=col;
        }
        for (int q=mid+1;q<N;q++)
        {
            E[q]=N;
        }
        xx=perform_experiment(E);
        if (xx==ochr) l=mid;
        else r=mid;
    }
    return r;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
    vector<int> G(N, -1);
    for (int col=0;col<=N-1;col++)
    {
        int ll=0;
        while (true)
        {
            int toi=find_ch(ll,N-1,col);
            if (toi==-1) break;
            G[toi]=col;
            ll=toi+2;
        }
        ll=1;
        while (true)
        {
            int toi=find_nc(ll,N-1,col);
            if (toi==-1) break;
            G[toi]=col;
            ll=toi+2;
        }
    }
    return G;
}

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