Submission #1291897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291897		simona1230	Chameleon's Love (JOI20_chameleon)	C++20	40 / 100	35 ms	568 KiB

chameleon

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

int n;
vector<int> v[512];
int u[512][512];

void subt()
{
    vector<int> g;
    for(int i=n+1; i<=2*n; i++)
        g.push_back(i);

    for(int i=1; i<=n; i++)
    {
        g.push_back(i);
        int qh=Query(g);
        //cout<<"! "<<qh<<endl;
        g.pop_back();

        int l=n+1,r=2*n;
        int v1=0,v2=0,v3=0;
        while(l<=r)
        {
            int m=(l+r)/2;
            vector<int> h= {i};
            for(int j=n+1; j<=m; j++)
                h.push_back(j);
            int k=m-n;
            int q=Query(h);
            if(q==k)
            {
                v1=m;
                r=m-1;
            }
            else if(q==k-1)
            {
                r=m-1;
            }
            else l=m+1;
        }

        if(qh==n)
        {
            //cout<<i<<" : "<<v1<<endl;
            v[i].push_back(v1);
            v[v1].push_back(i);
            continue;
        }

        l=n+1,r=2*n;
        while(l<=r)
        {
            int m=(l+r)/2;
            vector<int> h= {i};
            for(int j=m; j<=2*n; j++)
                h.push_back(j);
            int k=2*n-m+1;
            int q=Query(h);
            if(q==k)
            {
                v2=m;
                l=m+1;
            }
            else if(q==k-1)
            {
                l=m+1;
            }
            else r=m-1;
        }

        l=v1+1,r=v2-1;
        while(l<=r)
        {
            int m=(l+r)/2;
            vector<int> h= {i};
            for(int j=v1+1; j<=m; j++)
                h.push_back(j);
            int k=m-v1;
            int q=Query(h);
            if(q==k)
            {
                v3=m;
                r=m-1;
            }
            else if(q==k-1)
            {
                r=m-1;
            }
            else l=m+1;
        }

        v[i].push_back(v2);
        v[v2].push_back(i);
        v[i].push_back(v1);
        v[v1].push_back(i);
        v[i].push_back(v3);
        v[v3].push_back(i);
        //cout<<i<<": "<<v1<<" "<<v2<<" "<<v3<<endl;
    }
}

void Solve(int N)
{
    n=N;
    if(n>50)
    {
        subt();
    }
    else
    {
        for(int i=1; i<=2*N; i++)
        {
            for(int j=i+1; j<=2*N; j++)
            {
                int q=Query({i,j});
                if(q==1)
                {
                    v[i].push_back(j);
                    v[j].push_back(i);
                }
            }
        }
    }


    /*for(int i=1;i<=2*n;i++)
    {
        cout<<i<<" : ";
        for(int j=0;j<v[i].size();j++)
            cout<<v[i][j]<<" ";
        cout<<endl;
    }*/

    for(int i=1; i<=2*n; i++)
    {
        if(v[i].size()==3)
        {
            int v0=v[i][0],v1=v[i][1],v2=v[i][2];
            int q1=Query({v0,v1,i});
            int q2=Query({v0,v2,i});
            if(q1==1)u[i][v2]=u[v2][i]=1;
            else if(q2==1)u[i][v1]=u[v1][i]=1;
            else u[i][v0]=u[v0][i]=1;
        }
    }

    for(int i=1; i<=2*n; i++)
    {
        for(int j=0; j<v[i].size(); j++)
        {
            int nb=v[i][j];
            if(i<nb&&!u[i][nb])
            {
                //cout<<i<<" "<<nb<<endl;
                Answer(i,nb);
            }
        }
    }
}

/*
4
0 0 0 0 1 1 1 1
1 2 3 4 1 2 3 4
7 5 8 6 2 3 4 1
*/

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