Submission #1021650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021650		12345678	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	34 ms	4440 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=1e3+5;
 
int vs[nx], v[nx][nx];
vector<int> d[nx], a, b;
 
void dfs(int u, int c)
{
    vs[u]=1;
    if (!c) a.push_back(u);
    else b.push_back(u);
    for (auto v:d[u]) if (!vs[v]) dfs(v, !c); 
}

bool search(int l, int r, int cur, vector<int> &x)
{
    vector<int> qrs;
    qrs.push_back(cur);
    for (int i=l; i<=r; i++) qrs.push_back(x[i]);
    return Query(qrs)!=qrs.size();
}

void Solve(int N) {
    for (int i=2; i<=2*N; i++) 
    {
        a.clear();
        b.clear();
        for (int j=1; j<=2*N; j++) vs[j]=0;
        for (int j=1; j<i; j++) if (!vs[j]) dfs(j, 0);
        while (!a.empty()&&search(0, a.size()-1, i, a))
        {
            int l=0, r=a.size();
            while (l<r)
            {
                int md=(l+r)/2;
                if (search(l, md, i, a)) r=md;
                else l=md+1;
            }
            d[i].push_back(a[l]);
            d[a[l]].push_back(i);
            vector<int> tmp;
            for (int i=0; i<l; i++) tmp.push_back(a[i]);
            for (int i=l+1; i<a.size(); i++) tmp.push_back(a[i]);
            a=tmp;
        }
        while (!b.empty()&&search(0, b.size()-1, i, b))
        {
            int l=0, r=b.size();
            while (l<r)
            {
                int md=(l+r)/2;
                if (search(l, md, i, b)) r=md;
                else l=md+1;
            }
            d[i].push_back(b[l]);
            d[b[l]].push_back(i);
            vector<int> tmp;
            for (int i=0; i<l; i++) tmp.push_back(b[i]);
            for (int i=l+1; i<b.size(); i++) tmp.push_back(b[i]);
            b=tmp;
        }
    }
    for (int j=1; j<=2*N; j++) vs[j]=0;
    for (int i=1; i<=2*N; i++)
    {
        if (vs[i]) continue;
        if (d[i].size()==1)
        {
            Answer(i, d[i][0]);
            vs[i]=vs[d[i][0]]=1;
            continue;
        }
        bool f=0;
        for (int j=0; j<2; j++)
        {
            vector<int> qrs;
            qrs.push_back(i);
            for (int k=0; k<3; k++) if (k!=j) qrs.push_back(d[i][k]);
            if (Query(qrs)==1)
            {
                f=1;
                v[i][d[i][j]]=v[d[i][j]][i]=1;
                break;
            }
        }
        if (!f) v[i][d[i][2]]=v[d[i][2]][i]=1;
    }
    for (int i=1; i<=2*N; i++)
    {
        if (vs[i]) continue;
        for (int j=0; j<3; j++) if (!vs[i]&&!vs[d[i][j]]&&!v[i][d[i][j]]) vs[i]=vs[d[i][j]]=1, Answer(i, d[i][j]);
    }
}

Compilation message (stderr)

chameleon.cpp: In function 'bool search(int, int, int, std::vector<int>&)':
chameleon.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     return Query(qrs)!=qrs.size();
      |            ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:47:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for (int i=l+1; i<a.size(); i++) tmp.push_back(a[i]);
      |                             ~^~~~~~~~~
chameleon.cpp:63:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for (int i=l+1; i<b.size(); i++) tmp.push_back(b[i]);
      |                             ~^~~~~~~~~

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