Submission #407011

#	Time	Username	Problem	Language	Result	Execution time	Memory
407011		doowey	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	80 ms	696 KiB

chameleon

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

int n;

const int N = 2000;
vector<int> E[N];

bool vis[N];
vector<int> pa, qa;

void dfs(int u, int bit){
    vis[u]=true;
    if(bit == 0){
        pa.push_back(u);
    }
    else{
        qa.push_back(u);
    }
    for(auto x : E[u]){
        if(!vis[x]){
            dfs(x, (bit ^ 1));
        }
    }
}

map<pii, int> lovely;

void add(int la, int lb){
    lovely[mp(la, lb)] = 1;
    lovely[mp(lb, la)] = 1;
}

bool has(vector<int> lis, int node){
    if(lis.empty()) return false;
    lis.push_back(node);
    if(Query(lis) == lis.size()) return false;
    return true;
}

void process(int node, vector<int> lis){
    if(has(lis, node)){
        int lf, rf;
        lf = 0, rf = (int)lis.size() - 1;
        int mid;
        vector<int> cc;
        while(lf < rf){
            mid = (lf + rf) / 2;
            cc.clear();
            for(int j = 0; j <= mid; j ++ ){
                cc.push_back(lis[j]);
            }
            if(has(cc, node)){
                rf = mid;
            }
            else{
                lf = mid + 1;
            }
        }
        int nex = lis[lf];
        E[node].push_back(nex);
        E[nex].push_back(node);
        cc.clear();
        for(int j = lf + 1 ; j < lis.size(); j ++ ){
            cc.push_back(lis[j]);
        }
        process(node, cc);
        return;
    }
}

void Solve(int _n) {
    n = _n;
    for(int i = 2; i <= 2 * n; i ++ ){
        for(int j = 1; j < i ; j ++ ){
            vis[j]=false;
        }
        pa.clear();
        qa.clear();
        for(int j = 1; j < i ; j ++ ){
            if(!vis[j]){
                dfs(j, 0);
            }
        }
        process(i, pa);
        process(i, qa);
    }
    int X, Y, Z;
    int n0, n1, n2;
    for(int i = 1; i <= 2 * n; i ++ ){
        if(E[i].size() == 3){
            X = E[i][0];
            Y = E[i][1];
            Z = E[i][2];
            n0 = Query({i, X, Y});
            n1 = Query({i, X, Z});
            n2 = Query({i, Y, Z});
            if(n0 == 2 && n1 == 2){
                add(i, X);
            }
            else if(n0 == 2 && n2 == 2){
                add(i, Y);
            }
            else{
                add(i, Z);
            }
        }
    }
    for(int i = 1; i <= 2 * n; i ++ ){
        for(auto x : E[i]){
            if(x > i && !lovely.count(mp(i, x))){
                Answer(i, x);
            }
        }
    }
}

Compilation message (stderr)

chameleon.cpp: In function 'bool has(std::vector<int>, int)':
chameleon.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     if(Query(lis) == lis.size()) return false;
      |        ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp: In function 'void process(int, std::vector<int>)':
chameleon.cpp:73:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int j = lf + 1 ; j < lis.size(); j ++ ){
      |                              ~~^~~~~~~~~~~~

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