Submission #212925

#	Time	Username	Problem	Language	Result	Execution time	Memory
212925		thebes	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	92 ms	936 KiB

chameleon

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

typedef vector<int> vi;
#define pb push_back

const int MN = 1005;
vi g[4], adj[MN], acc; int i, j, k, lo, hi, vs[MN], ord[MN], c, p[MN], ans[MN], lst;
set<int> ed[MN];
mt19937 mt(time(0));

int Query(const vi &vec);
void Answer(int a,int b);

void dfs(int n,int par){
    if(vs[n]) return;
    vs[n] = 1;
    lst = n;
    int pid = 0;
    for(int i=0;i<adj[n].size();i++){
        if(adj[n][i]==par){
            pid = i;
            break;
        }
    }
    int ot = (pid+1)%3;
    vi tmp;
    tmp.pb(n);
    tmp.pb(par);
    tmp.pb(adj[n][ot]);
    if(Query(tmp)!=1) ot=3-pid-ot;
    if(!ans[adj[n][ot]]){
        Answer(n,adj[n][ot]);
        ans[n]=ans[adj[n][ot]]=1;
    }
    dfs(adj[n][3-pid-ot],n);
}

void Solve(int N){
    N *= 2;
    for(i=1;i<=N;i++)
        ord[i] = i;
    shuffle(ord+1,ord+N+1,mt);
    for(i=1;i<=N;i++){
        int fs = 3;
        for(j=0;j<4;j++){
            if(g[j].empty()){
                fs=min(fs,j);
                continue;
            }
            acc.clear();
            acc.insert(acc.end(),g[j].begin(),g[j].end());
            acc.pb(ord[i]);
            if(Query(acc)!=acc.size()){
                while(1){
                    for(auto v : g[j])
                        if(!ed[ord[i]].count(v)) hi++;
                    lo=0; hi--;
                    while(lo<hi){
                        int m = (lo+hi)>>1;
                        acc.clear(); acc.pb(ord[i]);
                        for(k=c=0;k<g[j].size()&&c<=m;k++){
                            if(!ed[ord[i]].count(g[j][k])) acc.pb(g[j][k]), c++;
                        }
                        if(Query(acc)==acc.size()) lo=m+1;
                        else hi=m;
                    }
                    for(k=c=0;k<g[j].size()&&c<=lo;k++)
                        if(!ed[ord[i]].count(g[j][k])) c++;
                    adj[g[j][k-1]].pb(ord[i]);
                    adj[ord[i]].pb(g[j][k-1]);
                    ed[g[j][k-1]].insert(ord[i]);
                    ed[ord[i]].insert(g[j][k-1]);
                    acc.clear();
                    for(auto v : g[j])
                        if(!ed[ord[i]].count(v)) acc.pb(v);
                    if(acc.empty()) break;
                    acc.pb(ord[i]);
                    if(Query(acc)==acc.size()) break;
                }
            }
            else fs=min(fs,j);
        }
        g[fs].pb(ord[i]);
    }
    for(i=1;i<=N;i++){
        if(vs[i]) continue;
        if(ed[i].size()==1){
            if(!ans[i]){
                Answer(i,adj[i][0]);
                ans[i]=ans[adj[i][0]]=1;
            }
        }
        else{
            vs[i] = 1;
            acc.clear();
            acc.pb(i);
            acc.pb(adj[i][0]);
            acc.pb(adj[i][1]);
            if(Query(acc)==1){
                dfs(adj[i][2], i);
                int sm = 2;
                for(j=0;j<adj[i].size();j++)
                    if(adj[i][j]==lst) sm+=j;
                if(!ans[i]){
                    Answer(i,adj[i][3-sm]);
                    ans[i]=ans[adj[i][3-sm]]=1;
                }
                continue;
            }
            acc.clear();
            acc.pb(i);
            acc.pb(adj[i][0]);
            acc.pb(adj[i][2]);
            int sm = 0;
            if(Query(acc)==1) sm = 1;
            else sm = 0;
            dfs(adj[i][sm], i);
            for(j=0;j<adj[i].size();j++)
                if(adj[i][j]==lst) sm+=j;
            if(!ans[i]){
                Answer(i,adj[i][3-sm]);
                ans[i]=ans[adj[i][3-sm]]=1;
            }
        }
    }
}

Compilation message (stderr)

chameleon.cpp: In function 'void dfs(int, int)':
chameleon.cpp:21:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[n].size();i++){
                 ~^~~~~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:55:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(Query(acc)!=acc.size()){
                ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp:63:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for(k=c=0;k<g[j].size()&&c<=m;k++){
                                   ~^~~~~~~~~~~~
chameleon.cpp:66:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         if(Query(acc)==acc.size()) lo=m+1;
                            ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp:69:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for(k=c=0;k<g[j].size()&&c<=lo;k++)
                               ~^~~~~~~~~~~~
chameleon.cpp:80:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(Query(acc)==acc.size()) break;
                        ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp:104:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(j=0;j<adj[i].size();j++)
                         ~^~~~~~~~~~~~~~
chameleon.cpp:120:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=0;j<adj[i].size();j++)
                     ~^~~~~~~~~~~~~~

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