Submission #1291987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291987		simona1230	카멜레온의 사랑 (JOI20_chameleon)	C++20	24 / 100	32 ms	4328 KiB

chameleon

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

int n;
vector<int> v[1024];
int u[1024][1024];
vector<int> f1,f2;

void add(int i,int j)
{
    //cout<<i<<" + "<<j<<endl;
    v[i].push_back(j);
    v[j].push_back(i);
}

void subt()
{
    f1.push_back(1);
    for(int i=2;i<=2*n;i++)
    {
        f1.push_back(i);
        int q=Query(f1);
        if(q==f1.size())continue;

        f1.pop_back();
        f2.push_back(i);
        q=Query(f2);
    }

    vector<int> g;
    for(int i=0; i<f1.size(); i++)
        g.push_back(f1[i]);
    /*for(int i=0;i<n;i++)
        cout<<f1[i]<<" ";
    cout<<endl;
    for(int i=0;i<n;i++)
        cout<<f2[i]<<" ";
    cout<<endl;*/

    for(int i=0; i<f2.size(); i++)
    {
        g.push_back(f2[i]);
        int qh=Query(g);
        ///cout<<"! "<<f2[i]<<endl;
        g.pop_back();

        int l=0,r=f1.size()-1;
        int v1=0,v2=0,v3=0;
        while(l<=r)
        {
            int m=(l+r)/2;
            vector<int> h= {f2[i]};
            for(int j=0; j<=m; j++)
                h.push_back(f1[j]);
            int k=m+1;
            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[f2[i]].push_back(f1[v1]);
            v[f1[v1]].push_back(f2[i]);
            continue;
        }

        l=0,r=n-1;
        while(l<=r)
        {
            int m=(l+r)/2;
            vector<int> h= {f2[i]};
            for(int j=m; j<f1.size(); j++)
                h.push_back(f1[j]);
            int k=n-m;
            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= {f2[i]};
            for(int j=v1+1; j<=m; j++)
                h.push_back(f1[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;
        }

        add(f2[i],f1[v1]);
        add(f2[i],f1[v2]);
        add(f2[i],f1[v3]);
        //cout<<i<<": "<<v1<<" "<<v2<<" "<<v3<<endl;
    }
}

void Solve(int N)
{
    n=N;
    if(1)
    {
        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: 4 / 4
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 36