제출 #1280157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280157		janson0109	카멜레온의 사랑 (JOI20_chameleon)	C++20	100 / 100	45 ms	592 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long  ll;
typedef long double ld;
using namespace std;
const ll M = 998244353;

int quer(vector<int> &v) {
    vector<int> u;
    for(auto & x : v) u.push_back(x+1);
    return Query(u);
}

pair<int,int> searche(vector<int> a, int b) {
    if(a.size() == 1) return make_pair(a[0], b);
    vector<int> c, d;
    for(int i=0; i<a.size(); i++) {
        if(i % 2 == 0) c.push_back(a[i]);
        else d.push_back(a[i]);
    }
    vector<int> e = c;
    e.push_back(b);
    if(quer(e) != e.size()) return searche(c, b);
    else return searche(d, b);
}

void dfs(int root, vector<vector<int>> &e, vector<int> &visited, int cur) {
    visited[root] = cur;
    for(auto & v : e[root]) if(visited[v] == 0) dfs(v, e, visited, -cur);
}

void Solve(int N) {
    vector<vector<int>> e(2*N);
    for(int k=1; k<2*N; k++) {
        vector<int> visited(k,0);
        for(int i=0; i<k; i++) if(visited[i] == 0) dfs(i, e, visited, 1);
        vector<int> a,b;
        for(int i=0; i<k; i++) {
            if(visited[i] == 1) a.push_back(i);
            else b.push_back(i);
        }
        vector<int> c=a, d=b; c.push_back(k); d.push_back(k);
        while(quer(c) != c.size()) {
            pair<int,int> p = searche(a, k);
            e[p.F].push_back(p.S);
            e[p.S].push_back(p.F);
            a.erase(find(a.begin(), a.end(), e[k].back()));
            c.erase(find(c.begin(), c.end(), e[k].back()));
        }
        while(quer(d) != d.size()) {
            pair<int,int> p = searche(b, k);
            e[p.F].push_back(p.S);
            e[p.S].push_back(p.F);
            b.erase(find(b.begin(), b.end(), e[k].back()));
            d.erase(find(d.begin(), d.end(), e[k].back()));
        }
    }
    set<pair<int,int>> pairs;
    vector<vector<int>> e2(2*N);
    for(int i=0; i<2*N; i++) {
        if(e[i].size() == 1) pairs.insert(make_pair(min(i,e[i][0]), max(i,e[i][0])));
        else {
            vector<int> vec = {i, e[i][0], e[i][1], e[i][2]};
            for(int j=0; j<3; j++) {
                vector<int> guess = vec;
                guess.erase(find(guess.begin(), guess.end(), e[i][j]));
                if(quer(guess) == 1) {
                    e2[i].push_back(e[i][j]);
                    e2[e[i][j]].push_back(i);
                }
            }
        }
    }
    for(int i=0; i<2*N; i++) for(int j=i+1; j<2*N; j++) {
        if(find(e[i].begin(), e[i].end(), j) != e[i].end() && find(e2[i].begin(), e2[i].end(), j) == e2[i].end()) pairs.insert(make_pair(i,j));
    }
    for(auto & p : pairs) Answer(p.F + 1, p.S + 1);
}

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