제출 #365502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365502		valerikk	카멜레온의 사랑 (JOI20_chameleon)	C++17	0 / 100	22 ms	368 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h> 
using namespace std;

int query(vector<int> p) {
    return Query(p);
}

void answer(int a, int b) {
    Answer(a, b);
}

const int N = 505;

vector<int> g[2 * N];
int color[2 * N];
vector<int> component[2];

void dfs(int u) {
    component[color[u]].push_back(u);
    for (int v : g[u]) {
        if (color[v] == -1) {
            color[v] = color[u] ^ 1;
            dfs(v);
        }
    }   
}

int my_query(int i, int j) {
    auto p = component[color[i]];
    p.push_back(j);
    return query(p);
}

void solve(int n) {
    vector<pair<int, int>> pairs;
    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 1; j < i; j++) {
            if (query(vector<int>{i, j}) == 1) 
                pairs.emplace_back(i, j);
        }
    }
    
    for (auto [i, j] : pairs) {
        g[i].push_back(j);
        g[j].push_back(i);
    }

    for (int i = 1; i <= 2 * n; i++) 
        color[i] = -1;
    for (int i = 1; i <= 2 * n; i++) {
        if (color[i] == -1) {
            color[i] = 0;
            dfs(i);
        }
    }

    for (auto [i, j] : pairs) {
        int ij = my_query(i, j), ji = my_query(j, i);
        if ((ij == n && ji == n) || (ij == n && ji == n - 1) || (ji == n && ij == n - 1)) 
            answer(i, j);
    }
}

void Solve(int N) {
    solve(N);
}

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