Submission #156910

#	Time	Username	Problem	Language	Result	Execution time	Memory
156910		popovicirobert	Minerals (JOI19_minerals)	C++14	100 / 100	116 ms	3316 KiB

minerals

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

using namespace std;

void solve(vector <int> &l, vector <int> &r, bool ok) {
	if(l.empty()) {
		return ;
	}
	if(l.size() == 1) {
		Answer(l[0], r[0]);
		return ;
	}

	random_shuffle(l.begin(), l.end());
	random_shuffle(r.begin(), r.end());
	
	int mid = (0 + l.size()) / 3;
	vector <int> l1, l2;
	int i, ans = 0;
	for(i = 0; i <= mid; i++) {
		l1.push_back(l[i]);
		ans = Query(l[i]);
	}
	for(i = mid + 1; i < l.size(); i++) {
		l2.push_back(l[i]);
	}
	vector <int> r1, r2;
	for(i = 0; i < r.size(); i++) {
		if(r1.size() == l1.size()) {
			r2.push_back(r[i]);
			continue;
		}
		if(r2.size() == l2.size()) {
			r1.push_back(r[i]);
			continue;
		}
		int cur = Query(r[i]);
		if(cur == ans) {
			if(ok == 0) {
				r1.push_back(r[i]);
			}
			else {
				r2.push_back(r[i]);
			}
		}
		else {
			if(ok == 0) {
				r2.push_back(r[i]);
			}
			else {
				r1.push_back(r[i]);
			}
		}
		ans = cur;
		//Query(r[i]);
	}

	solve(l1, r1, ok ^ 1);
	solve(l2, r2, ok);
}

void Solve(int n) {
	srand(time(NULL));
	vector <int> l, r;
	int ans = 0;
	for(int i = 0; i < 2 * n; i++) {
		int cur = Query(i + 1);
		if(cur == ans) {
			l.push_back(i + 1);
		}
		else {
			r.push_back(i + 1);
		}
		ans = cur;
	}
	solve(l, r, 1);
}

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:25:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = mid + 1; i < l.size(); i++) {
                   ~~^~~~~~~~~~
minerals.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < r.size(); i++) {
             ~~^~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10