Submission #1229231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229231		PVM_pvm	스핑크스 (IOI24_sphinx)	C++20	3 / 100	13 ms	440 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;
        ochr=mid-le+1;
        if (mid==le)
        {
            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==0) 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;
    }
    assert(r%2==0);
    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)
        {
            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;
    }
    assert(r%2==1);
    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: 0 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36