Submission #1189736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189736		Double_Slash	Chameleon's Love (JOI20_chameleon)	C++20	100 / 100	25 ms	496 KiB

chameleon

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

using namespace std;
#define all(x) x.begin(), x.end()

vector<int> adj[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 Solve(int N) {
    vector<int> arr(N << 1);
    iota(all(arr), 1);
    recurse(arr);
    for (int i = 1; i <= N * 2; ++i) {
        if (adj[i].size() != 3) continue;
        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