Submission #233803

#	Time	Username	Problem	Language	Result	Execution time	Memory
233803		medk	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	87 ms	632 KiB

chameleon

#include <bits/stdc++.h>
#include "chameleon.h"

#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(u) (int)(u.size())
#define all(u) u.begin(),u.end()

using namespace std;

vector<vector<int>> g;

/*int Query(vector<int> qr)
{
    cout<<"he asked :";
    for(int x:qr) cout<<' '<<x;
    cout<<endl;
    int ret; cin>>ret;
    cout<<endl;
    return ret;
}

void Answer(int i, int j)
{
    cout<<"he answered "<<i<<' '<<j<<endl;
}*/

void genEdges(vector<int> v)
{
    vector<bool> queued(sz(v));
    vector<int> qu;
    for(int i=0;i<sz(v);i++)
    {
        bool flag=true;
        vector<int> to_query;
        for(int j=0;j<=i;j++)
        {
            if(queued[j]) continue;
            to_query.pb(v[j]);
        }
        while(1)
        {
            int get=Query(to_query);
            if(get==sz(to_query)) break;
            flag=false;
            int l=0,r=sz(to_query)-2;
            while(l<r)
            {
                int md=(l+r)/2+1;
                vector<int> toQ;
                for(int j=md;j<sz(to_query);j++)
                    toQ.pb(to_query[j]);
                get=Query(toQ);
                if(get==sz(toQ)) r=md-1;
                else l=md;
            }
            g[to_query[l]].pb(to_query.back());
            g[to_query.back()].pb(to_query[l]);
            to_query.erase(to_query.begin()+l);
        }
        if(!flag)
        {
            qu.pb(v[i]);
            queued[i]=1;
        }
    }
    for(int i=sz(v)-1;i>=0;i--)
    {
        if(!queued[i]) continue;
        vector<int> to_query;
        for(int j=sz(v)-1;j>=i;j--)
        {
            if(queued[j] && j!=i) continue;
            to_query.pb(v[j]);
        }
        while(1)
        {
            int get=Query(to_query);
            if(get==sz(to_query)) break;
            int l=0,r=sz(to_query)-2;
            while(l<r)
            {
                int md=(l+r)/2+1;
                vector<int> toQ;
                for(int j=md;j<sz(to_query);j++)
                    toQ.pb(to_query[j]);
                get=Query(toQ);
                if(get==sz(toQ)) r=md-1;
                else l=md;
            }
            g[to_query[l]].pb(to_query.back());
            g[to_query.back()].pb(to_query[l]);
            to_query.erase(to_query.begin()+l);
        }
    }
    if(sz(qu)) genEdges(qu);
}

void Solve(int N)
{
    g.resize(2*N+1);
    vector<int> tmp;
    for(int i=1;i<=2*N;i++) tmp.pb(i);
    genEdges(tmp);
    vector<bool> vis(2*N+1);
    for(int i=1;i<=2*N;i++)
    {
        if(vis[i]) continue;
        if(sz(g[i])==1)
        {
            Answer(i,g[i][0]);
            vis[g[i][0]]=1;
            vis[i]=1;
        }
    }
    for(int i=1;i<=2*N;i++)
    {
        if(vis[i]) continue;
        vector<int> candidates;
        for(int x:g[i]) if(!vis[x]) candidates.pb(x);
        if(sz(candidates)==1)
        {
            Answer(i,candidates[0]);
            vis[candidates[0]]=1;
            vis[i]=1;
        }
        else
        {
            for(int k=0;k<3;k++)
            {
                vector<int> ask;
                ask.pb(i);
                for(int j=0;j<3;j++)
                {
                    if(k==j) continue;
                    ask.pb(g[i][j]);
                }
                if(Query(ask)==1)
                {
                    vector<int> newask;
                    newask.pb(ask[1]);
                    for(int x:g[ask[1]])
                    {
                        if(x==i) continue;
                        newask.pb(x);
                    }
                    if(Query(newask)==1)
                    {
                        Answer(i,ask[2]);
                        vis[ask[2]]=1;
                    }
                    else
                    {
                        Answer(i,ask[1]);
                        vis[ask[1]]=1;
                    }
                    vis[i]=1;
                    break;
                }
            }
        }
    }
}
/*
int main()
{
    int N; cin>>N;
    Solve(N);
}*/

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