Submission #407008

#	Time	Username	Problem	Language	Result	Execution time	Memory
407008		doowey	카멜레온의 사랑 (JOI20_chameleon)	C++14	44 / 100	64 ms	604 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));
        }
    }
}

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

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;
    vector<int> ord;
    for(int i = 1; i <= 2 * n; i ++ ){
        ord.push_back(i);
    }
    random_shuffle(ord.begin(), ord.end());
    for(int i = 1; i < 2 * n; i ++ ){
        for(int j = 0; j < i ; j ++ ){
            vis[ord[j]]=false;
        }
        pa.clear();
        qa.clear();
        for(int j = 0; j < i ; j ++ ){
            if(!vis[ord[j]]){
                dfs(ord[j], 0);
            }
        }
        fin(ord[i], pa, 0, (int)pa.size() - 1, 1);
        fin(ord[i], qa, 0, (int)qa.size() - 1, 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 'int fin(int, std::vector<int>, int, int, int)':
chameleon.cpp:45:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |         if(party.size() == Q){
      |            ~~~~~~~~~~~~~^~~~

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