Submission #407002

#	Time	Username	Problem	Language	Result	Execution time	Memory
407002		doowey	Chameleon's Love (JOI20_chameleon)	C++14	44 / 100	51 ms	536 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 = 1001;
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));
        }
    }
}

void fin(int node, vector<int> ss, int lf, int rf){
    vector<int> party;
    party.push_back(node);
    for(int i = lf; i <= rf; i ++ ){
        party.push_back(ss[i]);
    }
    int Q = Query(party);
    if(party.size() == Q){
        return;
    }
    if(lf == rf){
        E[node].push_back(ss[lf]);
        E[ss[lf]].push_back(node);
        return;
    }
    int mid = (lf + rf) / 2;
    fin(node, ss, lf, mid);
    fin(node, ss, mid + 1, rf);
}

map<pii, int> lovely;

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

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);
            }
        }
        fin(i, pa, 0, (int)pa.size() - 1);
        fin(i, qa, 0, (int)qa.size() - 1);
    }
    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 'void fin(int, std::vector<int>, int, int)':
chameleon.cpp:43:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     if(party.size() == Q){
      |        ~~~~~~~~~~~~~^~~~

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