| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 51106 | shoemakerjo | ICC (CEOI16_icc) | 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 <bits/stdc++.h>
#include "icc.h"
#define maxn 102
using namespace std;
int n;
vector<vector<int>> comps;
vector<vector<int>> adj(maxn);
vector<int> curcomp;
bool vis[maxn];
const bool debug = false;
void flood(int u) { //complexity of this does not really matter
if (vis[u]) return;
vis[u] = true;
curcomp.push_back(u);
for (int v : adj[u]) flood(v);
}
// void setRoad(int a, int b) {
// //comment this function out later
// }
// int query(int size_a, int size_b, int a[], int b[]) {
// //comment this function out later
// cout << "query: " << size_a << " " << size_b << ": " << endl;
// cout << " ";
// for (int i = 0; i <size_a ; i++) {
// cout << a[i] << " ";
// }
// cout << endl;
// cout << " ";
// for (int i = 0; i < size_b; i++) {
// cout << b[i] << " ";
// }
// cout << endl;
// int ans;
// cin >> ans;
// return ans;
// }
void addroad(int a, int b) {
if (debug) cout << "ADD ROAD: " << a << " to " << b << endl;
adj[a].push_back(b);
adj[b].push_back(a);
setRoad(a, b); //this is the grader function
}
void run(int N) {
n = N;
for (int it = 0; it < N-1; it++) {
comps.clear();
fill(vis, vis+maxn, false);
for (int i = 1; i <= N; i++) {
if (!vis[i]) {
curcomp.clear();
flood(i);
comps.push_back(curcomp);
}
}
vector<vector<int>> left; //put each group in this
vector<vector<int>> right; //put a group in this
vector<int> vc;
for (int i = 0; i < (comps.size()+1)/2; i++) {
vc.push_back(i);
}
left.push_back(vc);
vector<int> vc2;
for (int i = (comps.size()+1)/2; i < comps.size(); i++) {
vc2.push_back(i);
}
right.push_back(vc2);
//do a check with everything
//if the check is false, separate each individual vector into 2 groups and send one to each side
//if the check is true, break out
bool fin = false;
while (!fin) {
vector<int> a, b;
for (vector<int> cur : left) {
for (int val : cur) {
for (int spot : comps[val]) {
a.push_back(spot);
}
}
}
for (vector<int> cur : right) {
for (int val : cur) {
for (int spot : comps[val]) {
b.push_back(spot);
}
}
}
int a2[a.size()];
int b2[b.size()];
for (int i = 0; i < a.size(); i++) {
a2[i] = a[i];
}
for (int i = 0; i < b.size(); i++) {
b2[i] = b[i];
}
int ans = query(a.size(), b.size(), a2, b2);
if (ans == 1) {
fin = true;
break;
}
else {
vector<vector<int>> l2;
vector<vector<int>> r2; //replacement for right
//something something
for (vector<int> cur : left) {
//split this in half
vector<int> c1, c2;
for (int i = 0; i < (cur.size()+1)/2; i++) {
c1.push_back(cur[i]);
}
for (int i = (cur.size()+1)/2; i < cur.size(); i++) {
c2.push_back(cur[i]);
}
l2.push_back(c1);
r2.push_back(c2);
}
for (vector<int> cur : right) {
//split this in half
vector<int> c1, c2;
for (int i = 0; i < (cur.size()+1)/2; i++) {
c1.push_back(cur[i]);
}
for (int i = (cur.size()+1)/2; i < cur.size(); i++) {
c2.push_back(cur[i]);
}
l2.push_back(c1);
r2.push_back(c2);
}
left.clear();
right.clear();
for (vector<int> cur : l2) {
left.push_back(cur);
}
for (vector<int> cur : r2) {
right.push_back(cur);
}
}
}
//now we can separate left and right into the individual values and do a binary search or something
if (debug) cout << "two groups share the edge " << endl;
int a = -1;
int b = -1; //the two things that connect their edge
vector<int> lstuff, rstuff;
for (vector<int> cur : left) {
for (int val : cur) {
for (int spot : comps[val]) {
lstuff.push_back(spot);
}
}
}
for (vector<int> cur : right) {
for (int val : cur) {
for (int spot : comps[val]) {
rstuff.push_back(spot);
}
}
}
if (debug) {
cout << "lstuff: " ;
for (int val : lstuff) cout << val << " ";
cout << endl;
cout << "rstuff: ";
for (int val : rstuff) cout << val << " ";
cout << endl;
}
vector<int> curcheck;
int l2[lstuff.size()];
int ls = lstuff.size();
int r2[rstuff.size()];
int rs = rstuff.size();
for (int i = 0; i < lstuff.size(); i++) {
l2[i] = lstuff[i];
}
for (int i = 0; i < rstuff.size(); i++) {
r2[i] = rstuff[i];
}
while (lstuff.size() > 1) {
int ch[lstuff.size()/2];
for (int i = 0; i < (lstuff.size()+1)/2; i++) {
ch[i] = lstuff[i];
}
int gv = query(lstuff.size()/2, rs, ch, r2);
vector<int> nstuff;
if (gv == 1) {
for (int i = 0; i < (lstuff.size()+1)/2; i++) {
nstuff.push_back(lstuff[i]);
}
}
else {
for (int i = (lstuff.size()+1)/2; i < lstuff.size(); i++) {
nstuff.push_back(lstuff[i]);
}
}
lstuff.clear();
for (int val : nstuff) {
lstuff.push_back(val);
}
}
a = lstuff[0];
while (rstuff.size() > 1) {
int ch[rstuff.size()/2];
for (int i = 0; i < (rstuff.size()+1)/2; i++) {
ch[i] = rstuff[i];
}
int gv = query(rstuff.size()/2, ls, ch, l2);
vector<int> nstuff;
if (gv == 1) {
for (int i = 0; i < (rstuff.size()+1)/2; i++) {
nstuff.push_back(rstuff[i]);
}
}
else {
for (int i = (rstuff.size()+1)/2; i < rstuff.size(); i++) {
nstuff.push_back(rstuff[i]);
}
}
rstuff.clear();
for (int val : nstuff) {
rstuff.push_back(val);
}
}
b = rstuff[0];
addroad(a, b);
}
}
int main() {
run(4); //just for local test
}
//void setRoad(int a, int b)
//int query(int size_a, int size_b, int a[], int b[])
// returns 1 if something from a group to b group
// returns 0 otherwise