| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 51109 |
2018-06-16T04:47:03 Z |
shoemakerjo |
ICC (CEOI16_icc) |
C++14 |
|
158 ms |
1168 KB |
#include <bits/stdc++.h>
#include "icc.h"
//above changes and LOCAL changes on submit
#define maxn 102
using namespace std;
// #define LOCAL
int n;
vector<vector<int>> comps;
vector<vector<int>> adj(maxn);
vector<int> curcomp;
bool vis[maxn];
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);
}
#ifdef LOCAL
void setRoad(int a, int b) {
//comment this function out later
}
#endif
#ifdef LOCAL
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;
}
#endif
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()+1)/2];
for (int i = 0; i < (lstuff.size()+1)/2; i++) {
ch[i] = lstuff[i];
}
int gv = query((lstuff.size()+1)/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()+1)/2];
for (int i = 0; i < (rstuff.size()+1)/2; i++) {
ch[i] = rstuff[i];
}
int gv = query( (rstuff.size()+1)/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);
}
}
#ifdef LOCAL
int main() {
debug = true;
run(4); //just for local test
cin >> debug;
}
#endif
//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
Compilation message
icc.cpp: In function 'void run(int)':
icc.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < (comps.size()+1)/2; i++) {
~~^~~~~~~~~~~~~~~~~~~~
icc.cpp:81:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = (comps.size()+1)/2; i < comps.size(); i++) {
~~^~~~~~~~~~~~~~
icc.cpp:107:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.size(); i++) {
~~^~~~~~~~~~
icc.cpp:110:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < b.size(); i++) {
~~^~~~~~~~~~
icc.cpp:126:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < (cur.size()+1)/2; i++) {
~~^~~~~~~~~~~~~~~~~~
icc.cpp:129:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = (cur.size()+1)/2; i < cur.size(); i++) {
~~^~~~~~~~~~~~
icc.cpp:138:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < (cur.size()+1)/2; i++) {
~~^~~~~~~~~~~~~~~~~~
icc.cpp:141:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = (cur.size()+1)/2; i < cur.size(); i++) {
~~^~~~~~~~~~~~
icc.cpp:194:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < lstuff.size(); i++) {
~~^~~~~~~~~~~~~~~
icc.cpp:197:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < rstuff.size(); i++) {
~~^~~~~~~~~~~~~~~
icc.cpp:203:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < (lstuff.size()+1)/2; i++) {
~~^~~~~~~~~~~~~~~~~~~~~
icc.cpp:209:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < (lstuff.size()+1)/2; i++) {
~~^~~~~~~~~~~~~~~~~~~~~
icc.cpp:214:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = (lstuff.size()+1)/2; i < lstuff.size(); i++) {
~~^~~~~~~~~~~~~~~
icc.cpp:226:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < (rstuff.size()+1)/2; i++) {
~~^~~~~~~~~~~~~~~~~~~~~
icc.cpp:232:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < (rstuff.size()+1)/2; i++) {
~~^~~~~~~~~~~~~~~~~~~~~
icc.cpp:237:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = (rstuff.size()+1)/2; i < rstuff.size(); i++) {
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
504 KB |
Ok! 95 queries used. |
| 2 |
Correct |
10 ms |
740 KB |
Ok! 104 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
740 KB |
Ok! 542 queries used. |
| 2 |
Correct |
48 ms |
892 KB |
Ok! 632 queries used. |
| 3 |
Correct |
57 ms |
956 KB |
Ok! 637 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
956 KB |
Ok! 1387 queries used. |
| 2 |
Correct |
149 ms |
956 KB |
Ok! 1605 queries used. |
| 3 |
Correct |
155 ms |
1040 KB |
Ok! 1628 queries used. |
| 4 |
Correct |
134 ms |
1044 KB |
Ok! 1487 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
1044 KB |
Ok! 1425 queries used. |
| 2 |
Correct |
136 ms |
1076 KB |
Ok! 1422 queries used. |
| 3 |
Correct |
157 ms |
1088 KB |
Ok! 1524 queries used. |
| 4 |
Correct |
142 ms |
1144 KB |
Ok! 1499 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
1144 KB |
Ok! 1550 queries used. |
| 2 |
Correct |
138 ms |
1144 KB |
Ok! 1488 queries used. |
| 3 |
Correct |
152 ms |
1152 KB |
Ok! 1617 queries used. |
| 4 |
Correct |
136 ms |
1152 KB |
Ok! 1524 queries used. |
| 5 |
Correct |
149 ms |
1164 KB |
Ok! 1446 queries used. |
| 6 |
Correct |
134 ms |
1164 KB |
Ok! 1516 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
147 ms |
1168 KB |
Ok! 1524 queries used. |
| 2 |
Correct |
158 ms |
1168 KB |
Ok! 1574 queries used. |
