| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 234703 | anonymous | Chameleon's Love (JOI20_chameleon) | C++14 | 0 ms | 0 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 <vector>
#include <cassert>
#include <iostream>
#define MAXN 1005
using namespace std;
vector <int> adj[MAXN];
vector <int> M, F;
int Num, Love[MAXN], vis[MAXN], Done[MAXN];
voidfindEdge(int i, vector<int> IS) {
IS.push_back(i);
if (Num == 3 || IS.size() == 1 || Query(IS) == IS.size()) {return(0);}
if (IS.size() == 2) {
adj[i].push_back(IS[0]);
adj[IS[0]].push_back(i);
Num++;
} else {
IS.pop_back();
vector <int> L, R;
int mid = (IS.size() - 1)/2;
for (int i=0; i < IS.size(); i++) {
if (i <= mid) {L.push_back(IS[i]);}
else {R.push_back(IS[i]);}
}
findEdge(i, L);
findEdge(i, R);
}
}
void dfs(int u, int t, bool c) {
vis[u] = t;
if (c) {M.push_back(u);}
else {F.push_back(u);}
for (int v: adj[u]) {
if (vis[v] != t) {dfs(v, t, c^1);}
}
}
void bipartite(int t) {
M.clear();
F.clear();
for (int i=1; i<t; i++) {
if (vis[i] != t) {dfs(i,t,0);}
}
}
void Solve(int N) {
for (int i=1; i<=2*N; i++) {
Num = 0;
bipartite(i);
findEdge(i, M);
findEdge(i, F);
}
for (int i=1; i<=2*N; i++) {
assert(adj[i].size() == 1 || adj[i].size() == 3);
if (adj[i].size() != 3) {
if (adj[i][0] > i || adj[adj[i][0]].size() == 3) {Answer(i, adj[i][0]);}
continue;
}
for (int j=0; j<3; j++) {
vector <int> Ask;
Ask.push_back(i);
for (int k=0; k<3; k++) {
if (j != k) {Ask.push_back(adj[i][k]);}
}
if (Query(Ask) == 1) {
Love[i] = adj[i][j];
break;
}
}
}
bipartite(2*N+1);
for (int f: F) {
for (int m: adj[f]) {
if (Love[m] != f && Love[f] != m && adj[f].size() == 3 && adj[m].size() == 3) {
Answer(f,m);
}
}
}
}