Submission #119850

#	Time	Username	Problem	Language	Result	Execution time	Memory
119850		keko37	Meetings (JOI19_meetings)	C++14	100 / 100	1159 ms	1040 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"


using namespace std;

int n;

void rjesi (vector <int> v) {
	if (v.size() < 2) return;
	random_shuffle(v.begin(), v.end());
	int a = v[0], b = v[1];
	vector <int> lef, rig;
	lef.push_back(a); rig.push_back(b);
	for (int i=2; i<v.size(); i++) {
		//cout << "pikam " << a << " " << b << " " << v[i] << endl;
		if (v[i] == a || v[i] == b) continue;
		assert(a != b);
		int val = Query(a, b, v[i]);
		if (val == a) {
			lef.push_back(v[i]);
		} else if (val == b) {
		 	rig.push_back(v[i]);
		} else {
			if (lef.size() < rig.size()) {
				a = val;
				lef.push_back(val);
				if (v[i] != val) lef.push_back(v[i]);
			} else {
				b = val;
				rig.push_back(val);
				if (v[i] != val) rig.push_back(v[i]);
			}
		}
	}
	if (a > b) swap(a, b);
	//cout << "naso sam " << a << " " << b << endl;
	//cout << "lef je "; for (auto x : lef) cout << x << " "; cout << endl;
	//cout << "rig je "; for (auto x : rig) cout << x << " "; cout << endl;
	Bridge(a, b);
	sort(lef.begin(), lef.end());
	lef.erase(unique(lef.begin(), lef.end()), lef.end());
	sort(rig.begin(), rig.end());
	rig.erase(unique(rig.begin(), rig.end()), rig.end());
	rjesi(lef);
	rjesi(rig);
}

void Solve (int N) {
	n = N;
	vector <int> e;
	for (int i=0; i<n; i++) {
		e.push_back(i);
	}
	rjesi(e);
}

Compilation message (stderr)

meetings.cpp: In function 'void rjesi(std::vector<int>)':
meetings.cpp:15:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=2; i<v.size(); i++) {
                ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71