제출 #1189735

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

chameleon

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

using namespace std;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;

vector<int> adj[1001];
bool done[1001];
int nxt[1001];

int dnc(int i, vector<int>::iterator l, vector<int>::iterator r) {
    if (r - l == 1) return *l;
    auto m = l + (r - l) / 2;
    vector<int> arr(l, m);
    arr.emplace_back(i);
    if (Query(arr) < arr.size()) return dnc(i, l, m);
    else return dnc(i, m, r);
}

void recurse(const vector<int> &arr) {
    if (arr.size() <= 1) return;
    vector<int> a, b;
    for (int i: arr) {
        a.emplace_back(i);
        if (a.size() > 1 and Query(a) < a.size()) {
            a.pop_back();
            b.emplace_back(i);
        }
    }
    for (int i: b) {
        for (vector<int> cur = a; not cur.empty();) {
            int j = dnc(i, all(cur));
            adj[i].emplace_back(j);
            adj[j].emplace_back(i);
            cur.erase(find(all(cur), j));
            cur.emplace_back(i);
            if (Query(cur) == cur.size()) break;
            cur.pop_back();
        }
    }
    recurse(b);
}

void dfs(int i, int par, bool b) {
    adj[i].erase(find(all(adj[i]), par));
    if (nxt[i]) return;
    done[i] = true;
    assert(adj[i].size() == 1);
    if (b) Answer(i, adj[i][0]);
    dfs(adj[i][0], i, not b);
}

void Solve(int N) {
    vector<int> arr(N << 1);
    iota(all(arr), 1);
    recurse(arr);
    // for (int i = 1; i <= 2 * N; ++i) {
    //     for (int j: adj[i]) cerr << i << " " << j << endl;
    // }
    // cerr << endl;
    bool done[N * 2 + 1]{};
    int type[N * 2 + 1]{};
    vector<pint> rem;
    for (int i = 1; i <= N * 2; ++i) {
        if (adj[i].size() == 1) {
            done[i] = done[adj[i][0]] = true;
        } else if (adj[i].size() == 3) {
            if (Query({i, adj[i][0], adj[i][1]}) == 1) nxt[i] = adj[i][2];
            else if (Query({i, adj[i][0], adj[i][2]}) == 1) nxt[i] = adj[i][1];
            else nxt[i] = adj[i][0];
            adj[i].erase(find(all(adj[i]), nxt[i]));
        }
    }
    for (int i = 1; i <= N * 2; ++i) {
        if (nxt[i]) adj[nxt[i]].erase(find(all(adj[nxt[i]]), i));
    }
    for (int i = 1; i <= N * 2; ++i) {
        if (adj[i][0] > i) Answer(i, adj[i][0]);
    }
}

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