Submission #1306813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306813		Sharky	Chameleon's Love (JOI20_chameleon)	C++20	100 / 100	48 ms	556 KiB

chameleon

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

namespace {

const int N = 1001;
bool vis[N], ans[N];
int c[N];
vector<int> adj[N], v[2];
bool ban[N][3];

}  // namespace



void dfs(int u) {
    vis[u] = true;
    v[c[u]].push_back(u);
    for (int v : adj[u]) if (!vis[v]) {
        c[v] = c[u] ^ 1;
        dfs(v);
    }
}

void helper(int a, int b) {
    if (ans[a] || ans[b]) return;
    ans[a] = ans[b] = true;
    Answer(a, b);
}

void Solve(int n) {
    for (int i = 2; i <= 2 * n; i++) {
        for (int j = 1; j <= i; j++) vis[j] = false;
        v[0].clear(); v[1].clear();
        for (int j = 1; j < i; j++) if (!vis[j]) dfs(j);
        for (int j = 0; j < 2; j++) {
            while (true) {
                vector<int> q = v[j];
                q.push_back(i);
                int res = Query(q);
                if (res < q.size()) {
                    int l = 0, r = v[j].size() - 1;
                    while (l < r) {
                        q.clear();
                        int mid = (l + r) / 2;
                        for (int k = 0; k <= mid; k++) q.push_back(v[j][k]);
                        q.push_back(i);
                        res = Query(q);
                        if (res < q.size()) r = mid;
                        else l = mid + 1;
                    }
                    adj[v[j][l]].push_back(i);
                    adj[i].push_back(v[j][l]);
                    v[j].erase(v[j].begin() + l);
                } else break;
            }
        }
    }
    for (int i = 1; i <= 2 * n; i++) {
        if (ans[i]) continue;
        if ((int) adj[i].size() == 1) helper(i, adj[i][0]);
        if (ans[i]) continue;
        int r01 = Query({i, adj[i][0], adj[i][1]});
        int r12 = Query({i, adj[i][1], adj[i][2]});
        int loves;
        if (r01 == 2 && r12 == 2) loves = 1;
        else if (r01 == 2 && r12 == 1) loves = 0;
        else loves = 2;
        ban[i][loves] = true;
        int x = adj[i][loves];
        for (int j = 0; j < 3; j++) {
            if (adj[x][j] == i) ban[x][j] = true;
        }
    }
    for (int i = 1; i <= 2 * n; i++) {
        if (ans[i]) continue;
        int cnt = 0, idx = 0;
        for (int j = 0; j < adj[i].size(); j++) if (!ban[i][j]) cnt++, idx = j;
        helper(i, adj[i][idx]);
    }
}

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