# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
719958 | walterw | Chameleon's Love (JOI20_chameleon) | C++17 | 19 ms | 1360 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "chameleon.h"
#include <bits/stdc++.h>
namespace {
int variable_example = 1;
}
using namespace std;
int n;
vector<int> adj[10005];
int oneway[10005];
vector<int> leftovers[10005];
bool answered[00005];
void Solve(int N) {
n = N;
for (int i = 1; i <= 2 * n; i++) {
if (answered[i]) continue;
for (int j = 1; j <= 2 * n; j++) {
if (i == j) continue;
vector<int> temp = {i, j};
int res = Query(temp);
if (res == 1) {
// an edge
adj[i].push_back(j);
}
}
if (adj[i].size() == 1) {
// mutual love case
Answer(i, adj[i][0]);
answered[i] = answered[adj[i][0]] = true;
} else {
assert(adj[i].size() == 3);
int q1 = Query({i, adj[i][0], adj[i][1]});
int q2 = Query({i, adj[i][0], adj[i][2]});
int q3 = Query({i, adj[i][1], adj[i][2]});
if (q1 == 1) {
oneway[i] = adj[i][2];
leftovers[i] = {adj[i][0], adj[i][1]};
} else if (q2 == 1) {
oneway[i] = adj[i][1];
leftovers[i] = {adj[i][0], adj[i][2]};
} else {
oneway[i] = adj[i][0];
leftovers[i] = {adj[i][1], adj[i][2]};
}
}
}
for (int i = 1; i <= 2 * n; i++) {
if (answered[i]) continue;
if (adj[i].size() == 1) continue;
if (oneway[leftovers[i][0]] == i) {
Answer(i, leftovers[i][1]);
answered[i] = answered[leftovers[i][1]] =true;
} else {
Answer(i, leftovers[i][0]);
answered[i] = answered[leftovers[i][0]] =true;
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |