Submission #895358

#	Time	Username	Problem	Language	Result	Execution time	Memory
895358		box	Chameleon's Love (JOI20_chameleon)	C++17	40 / 100	2 ms	504 KiB

chameleon

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

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int MAXN = 505 * 2;

vector<int> adj[MAXN];
int who[MAXN], nex[MAXN], pre[MAXN];

void Solve(int N) {
    if (N <= 50) {
        for (int i = 1; i <= N * 2; i++)
            for (int j = i + 1; j <= N * 2; j++)
                if (Query({i, j}) == 1) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
        for (int i = 1; i <= N * 2; i++) {
            assert(sz(adj[i]) == 1 || sz(adj[i]) == 3);
            if (sz(adj[i]) == 1) {
                who[i] = adj[i][0];
            } else {
                nex[i] = [&]() {
                    if (Query({i, adj[i][0], adj[i][1]}) == 1) return adj[i][2];
                    if (Query({i, adj[i][0], adj[i][2]}) == 1) return adj[i][1];
                    return adj[i][0];
                }();
                pre[nex[i]] = i;
            }
        }
        for (int i = 1; i <= N * 2; i++) {
            if (!who[i]) {
                assert(sz(adj[i]) == 3);
                assert(pre[i] && nex[i]);
                who[i] = adj[i][0] ^ adj[i][1] ^ adj[i][2] ^ pre[i] ^ nex[i];
            }
            if (who[i] < i) Answer(who[i], i);
        }

    }
}

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