Submission #921128

#	Time	Username	Problem	Language	Result	Execution time	Memory
921128		abcvuitunggio	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	55 ms	604 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
    vector <int> ve[1001],tmp,V[2];
    int L[1001],c[1001],vis[1001],done[1001];
}
int get(int i, int l, int r, vector <int> v){
    tmp.clear();
    tmp.push_back(i);
    for (int i=l;i<=r;i++)
        tmp.push_back(v[i]);
    if (Query(tmp)==r-l+2)
        return -1;
    int lo=l,hi=r-1,kq=r;
    while (lo<=hi){
        int mid=(lo+hi)>>1;
        tmp.clear();
        tmp.push_back(i);
        for (int i=l;i<=mid;i++)
            tmp.push_back(v[i]);
        if (Query(tmp)<mid-l+2){
            kq=mid;
            hi=mid-1;
        }
        else
            lo=mid+1;
    }
    return kq;
}
vector <int> getall(int i, vector <int> v){
    int cur=0;
    vector <int> res;
    while (cur<v.size()&&res.size()<3){
        cur=get(i,cur,v.size()-1,v);
        if (cur==-1)
            break;
        res.push_back(v[cur]);
        cur++;
    }
    return res;
}
vector <int> operator +(vector <int> a, vector <int> b){
    for (int i:b)
        a.push_back(i);
    return a;
}
void dfs(int u, int C){
    if (vis[u])
        return;
    vis[u]=1;
    c[u]=C;
    V[C].push_back(u);
    for (int v:ve[u])
        dfs(v,C^1);
}
void Solve(int N){
    for (int i=1;i<=N*2;i++){
        memset(vis,0,sizeof(vis));
        memset(c,0,sizeof(c));
        V[0].clear();
        V[1].clear();
        for (int j=1;j<i;j++)
            if (!vis[j])
                dfs(j,0);
        ve[i]=getall(i,V[0])+getall(i,V[1]);
        for (int j:ve[i])
            ve[j].push_back(i);
    }
    for (int i=1;i<=N*2;i++){
        if (ve[i].size()==1){
            if (ve[i][0]>i){
                Answer(i,ve[i][0]);
                done[i]=done[ve[i][0]]=1;
            }
            continue;
        }
        if (Query({i,ve[i][0],ve[i][1]})<2){
            L[ve[i][2]]=i;
            continue;
        }
        if (Query({i,ve[i][0],ve[i][2]})<2){
            L[ve[i][1]]=i;
            continue;
        }
        L[ve[i][0]]=i;
    }
    for (int i=1;i<=N*2;i++){
        if (ve[i].size()>1&&L[i]&&!done[i]){
            vector <int> tmp={i,L[i]};
            for (int j:ve[i])
                if (j!=L[i])
                    tmp.push_back(j);
            int x=tmp.back();
            tmp.pop_back();
            int j=Query(tmp)<2?tmp.back():x;
            done[i]=done[j]=1;
            Answer(i,j);
            continue;
        }
    }
}

Compilation message (stderr)

chameleon.cpp: In function 'std::vector<int> getall(int, std::vector<int>)':
chameleon.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     while (cur<v.size()&&res.size()<3){
      |            ~~~^~~~~~~~~

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