Submission #55040

#	Time	Username	Problem	Language	Result	Execution time	Memory
55040		shoemakerjo	Library (JOI18_library)	C++14	100 / 100	703 ms	824 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;

#define vi vector<int>

int n;

int qu(vector<int>& fi, vector<vi>& se, int l, int r) { //eliminate unnecessary copying with &
	//stnadard query stuff
	vi guess(n);
	for (int i = 0; i < n; i++) guess[i] = 0;
	for (int val : fi) guess[val-1] = 1;
	for (int i = l; i <= r; i++) {
		vi vc = se[i];
		for (int val : vc) guess[val-1] = 1; //1-index them

	}
	return Query(guess);

}

vi inds; //store the indices
int nummelds = 0; //debugging tool if needed

void go(vi& le, vector<vi>& stuff, int l, int r) {
	if (l == r) {
		if (qu(le, stuff, l, r) == 1) {
			//good thing
			inds.push_back(l);

		}
		return;
	}
	if (qu(le, stuff, l, r) == (r-l + 2)) {
		return; //this is bad stuff
	}
	int mid = (l+r)/2;
	go(le, stuff, l, mid);
	go(le, stuff, mid+1, r);
}

// pintvec(vi& v1) {
// 	for (int val : v1) cout << val << " ";
// }

vector<vi> rec(int l, int r) {
	//this is the modified merge sort type thing
	vector<vector<int>> ans; //everything will be copied at most log n times
	if (l == r) {
		vi cur;
		cur.push_back(l);
		ans.push_back(cur);
		return ans;
	}
	int mid = (l+r)/2;
	vector<vi> le = rec(l, mid);
	vector<vi> re = rec(mid+1, r);
	for (int i = le.size()-1; i >= 0; i--) {
		vi vc = le[i];
		int cur = qu(vc, re, 0, re.size()-1);
		if (cur == re.size()+1) continue;
		inds.clear(); //just store the meld indices
		go(vc, re, 0, re.size()-1);

		vi nv; //new vector;
		vi bef; //put before my boy
		vi aft; //put after my boy

		vi tmp; //temporary stuff
		vector<vi> tp2;

		if (inds.size() == 2) {
			if (re[inds[0]].size() < re[inds[1]].size()) {
				swap(inds[0], inds[1]);
			}
		}

		for (int j = 0; j < inds.size(); j++) {
			int ic = inds[j]; //get the value
			// cout << "unioning ";
			// pintvec(vc);
			// cout << " to ";
			// pintvec(re[ic]);
			

			tmp.clear();
			tmp.push_back(vc[0]); 
			if (bef.size() == 0 && 
				qu(tmp, re, ic, ic) == 1) { //only 1 group
				//we know it is before me
				//if it is size one just make the first before
				//see which end meld
				// cout << " (type bef)";
				tmp.clear();
				tmp.push_back(re[ic][0]);
				tp2.clear();
				tp2.push_back(tmp);

				if (re[ic].size() == 1 || qu(vc, tp2, 0, 0) == 1) { 
					//first guy is linked
					// cout << " go first";
					for (int k = re[ic].size()-1; k >= 0; k--) {
						bef.push_back(re[ic][k]);
					}
				}
				else {
					// cout << "go second";
					for (int k = 0; k < re[ic].size(); k++) {
						bef.push_back(re[ic][k]);
					}
				}

			}
			else {
				// cout << "(type aft)";
				tmp.clear();
				tmp.push_back(re[ic][0]);
				tp2.clear();
				tp2.push_back(tmp);

				if (re[ic].size() == 1 || qu(vc, tp2, 0, 0) == 1) { 
					//first guy is linked
					// cout << " go first";
					for (int k = 0; k < re[ic].size(); k++) {
						aft.push_back(re[ic][k]);
					}
				}	
				else {
					// cout << " go second";
					for (int k = re[ic].size()-1; k >= 0; k--) {
						aft.push_back(re[ic][k]);
					}
				}
			}
			//cout << endl;


		}
		// cout << "before unions: ";
		// pintvec(vc);
		// cout << "  and then ";
		for (int val : bef) {
			nv.push_back(val);
		}
		for (int val : vc) {
			nv.push_back(val);
		}
		for (int val : aft) {
			nv.push_back(val);
		}
		// pintvec(nv);
		// cout << endl;
		sort(inds.begin(), inds.end());
		reverse(inds.begin(), inds.end());
		for (int cur : inds) {
			re.erase(re.begin()+cur);
		}

		//erase the used vector
		re.push_back(nv);
		le.erase(le.begin()+i); //take it out afterwards
	}
	for (vi vc : le) ans.push_back(vc);
	for (vi vc : re) ans.push_back(vc);
	return ans;
}

void Solve(int N)
{
	n = N;
	vector<vi> res = rec(1, n);
	assert(res.size() == 1);
	// cout << "my ans: ";
	// for (int val : res[0]) cout << val << " ";
	// cout << endl;
	Answer(res[0]);

}

Compilation message (stderr)

library.cpp: In function 'std::vector<std::vector<int> > rec(int, int)':
library.cpp:62:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (cur == re.size()+1) continue;
       ~~~~^~~~~~~~~~~~~~
library.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < inds.size(); j++) {
                   ~~^~~~~~~~~~~~~
library.cpp:109:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < re[ic].size(); k++) {
                      ~~^~~~~~~~~~~~~~~
library.cpp:125:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < re[ic].size(); k++) {
                      ~~^~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81