#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
void Alice(int N, int M, int A[], int B[]) {
// Graph
const int V = N + 11;
vector <pair <int, int> > edges;
for (int i = 0; i < M; ++ i)
edges.emplace_back(A[i], B[i]);
// Encode in binary
for (int i = 0; i < 10; ++ i) {
for (int j = 0; j < N; ++ j) {
if (j & (1 << i)) {
edges.emplace_back(N + i, j);
}
}
// Add control node edges
edges.emplace_back(N + 10, N + i);
}
// Generate random vector
mt19937 mt(123);
uniform_int_distribution <int> dist(0, 1);
// Add clique
for (int i = 0; i < 10; ++ i) {
for (int j = 0; j < i; ++ j) {
const bool val = dist(mt);
if (val)
edges.emplace_back(N + j, N + i);
}
}
// Send graph
const int U = edges.size();
InitG(V, U);
for (int i = 0; i < U; ++ i) {
MakeG(i, edges[i].first, edges[i].second);
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
void Bob(int V, int U, int C[], int D[]) {
// Graph
vector <vector <int> > graph(V, vector <int>());
set <pair <int, int> > graphEdges;
for (int i = 0; i < U; ++ i) {
graph[C[i]].push_back(D[i]);
graph[D[i]].push_back(C[i]);
graphEdges.insert(make_pair(C[i], D[i]));
graphEdges.insert(make_pair(D[i], C[i]));
}
// Map
const int N = V - 11;
vector <pair <int, int> > mapEdges;
mt19937 mt(123);
uniform_int_distribution <int> dist(0, 1);
int labels[10][10];
for (int i = 0; i < 10; ++ i) {
for (int j = 0; j < i; ++ j) {
const bool val = dist(mt);
labels[i][j] = val;
}
}
// Identify helper node
int node = -1;
vector <int> v;
for (int i = 0; i < V; ++ i) {
if (graph[i].size() == 10) {
bool found = false;
function <void(int)> backtr = [&](int pos) {
for (int index = 0; index + 1 < pos; ++ index)
if (graphEdges.count(make_pair(v[index], v[pos - 1])) != labels[pos - 1][index])
return ;
if (pos == 10) {
found = true;
return ;
}
for (int index = 0; index < graph[i].size(); ++ index) {
if (found)
break;
const int nd = graph[i][index];
swap(graph[i][index], graph[i].back());
graph[i].pop_back();
v.push_back(nd);
backtr(pos + 1);
if (!found)
v.pop_back();
graph[i].push_back(nd);
swap(graph[i][index], graph[i].back());
}
};
backtr(0);
if (found) {
node = i;
break;
}
}
}
// Find shuffle used
set <int> specials = {node};
for (int i = 0; i < 10; ++ i) {
const int node = v[i];
specials.insert(node);
}
vector <int> perm(V);
for (int i = 0; i < 10; ++ i)
const int node = v[i];
for (auto it: graph[node])
if (!specials.count(it))
perm[it] += (1 << i);
// Reconstruct edges
for (int i = 0; i < V; ++ i)
if (!specials.count(i))
for (auto it: graph[i])
if (!specials.count(it) && i < it)
mapEdges.push_back(make_pair(perm[i], perm[it]));
// Send graph
const int M = mapEdges.size();
InitMap(N, M);
for (int i = 0; i < M; ++ i) {
MakeMap(mapEdges[i].first, mapEdges[i].second);
}
}
Compilation message
Bob.cpp: In lambda function:
Bob.cpp:39:75: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (graphEdges.count(make_pair(v[index], v[pos - 1])) != labels[pos - 1][index])
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Bob.cpp:47:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int index = 0; index < graph[i].size(); ++ index) {
~~~~~~^~~~~~~~~~~~~~~~~
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:77:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < 10; ++ i)
^~~
Bob.cpp:79:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (auto it: graph[node])
^~~
Bob.cpp:78:19: warning: unused variable 'node' [-Wunused-variable]
const int node = v[i];
^~~~
Bob.cpp:81:35: error: 'i' was not declared in this scope
perm[it] += (1 << i);
^
Bob.cpp:81:35: note: suggested alternative: 'it'
perm[it] += (1 << i);
^
it
