Submission #51109

#	Time	Username	Problem	Language	Result	Execution time	Memory
51109		shoemakerjo	ICC (CEOI16_icc)	C++14	100 / 100	158 ms	1168 KiB

icc

#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 (stderr)

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++) {
                                       ~~^~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10