Submission #1302177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302177		simona1230	Chameleon's Love (JOI20_chameleon)	C++20	44 / 100	50 ms	4056 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn=1001;

int n;
vector<int> v[maxn];
vector<int> lf,rt;
int e[maxn][maxn];

void connect(int ver,vector<int> f)
{
    /*cout<<ver<<" > ";
    for(int i=0;i<f.size();i++)
        cout<<f[i]<<" ";
    cout<<endl;*/
    int bg=0;
    while(1)
    {
        int id=-1;
        int l=bg,r=f.size()-1;
        while(l<=r)
        {
            int m=(l+r)/2;
            int k=m-bg+2;
            vector<int> q={ver};
            for(int i=bg;i<=m;i++)
                q.push_back(f[i]);

            if(Query(q)!=k)
            {
                id=m;
                r=m-1;
            }
            else l=m+1;
        }

        if(id==-1)return;
        bg=id+1;
        id=f[id];
        v[ver].push_back(id);
        v[id].push_back(ver);
        e[ver][id]=e[id][ver]=1;
        //cout<<ver<<" -- "<<id<<endl;
    }

}

int u[maxn];

void dfs(int i,int c)
{
    if(c==1)lf.push_back(i);
    else rt.push_back(i);

    u[i]=1;
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(u[nb])continue;

        dfs(nb,c^2);
    }
}

void build()
{
    for(int i=1; i<=2*n; i++)
    {
        //cout<<"> "<<i<<endl;
        for(int j=1;j<i;j++)
            u[j]=0;
        for(int j=1; j<i;j++)
            if(!u[j])dfs(j,1);

        connect(i,lf);
        connect(i,rt);
        lf.clear();
        rt.clear();
    }
}


void Solve(int N)
{
    n=N;
    build();

    for(int i=1;i<=2*n;i++)
    {
        if(v[i].size()==1)
        {
            if(v[i][0]<i)
            {
                e[v[i][0]][i]=e[i][v[i][0]]=2;
                Answer(v[i][0],i);
            }
            continue;
        }


        int q2=Query({i,v[i][0],v[i][1]});
        int q1=Query({i,v[i][0],v[i][2]});
        if(q1==1)e[i][v[i][1]]=e[v[i][1]][i]=2;
        else if(q2==1)e[i][v[i][2]]=e[v[i][2]][i]=2;
        else e[i][v[i][0]]=e[v[i][0]][i]=2;
    }

    for(int i=1;i<=2*n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(e[i][j]==1)
            {
                Answer(j,i);
            }
        }
    }
}
/*
4
1 0 1 0 0 1 1 0
4 4 1 2 1 2 3 3
4 3 8 7 6 5 2 1
*/

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36