Submission #120991

#	Time	Username	Problem	Language	Result	Execution time	Memory
120991		gs14004	Minerals (JOI19_minerals)	C++17	100 / 100	73 ms	4660 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3000005;

void dnc(vector<int> l, vector<int> r, int toggle){
	if(l.size() == 1){
		Answer(l[0], r[0]);
		return;
	}
	int m = 0.35 * l.size(), last = 0;
	vector<int> ll, lr, rr, rl;
	m = max(m, 1); m = min(m, (int)l.size() - 1);
	for(int i=0; i<m; i++){
		last = Query(l[i]);
		ll.push_back(l[i]);
	}
	for(int i=m; i<l.size(); i++){
		lr.push_back(l[i]);
	}
	for(int i=0; i<r.size(); i++){
		if(rl.size() == ll.size()){
			rr.push_back(r[i]);
			continue;
		}
		if(rr.size() == lr.size()){
			rl.push_back(r[i]);
			continue;
		}
		int nxt = Query(r[i]);
		if(toggle ^ (nxt != last)){
			rr.push_back(r[i]);
		}
		else rl.push_back(r[i]);
		last = nxt;
	}
	dnc(ll, rl, toggle ^ 1);
	dnc(lr, rr, toggle);
}


void Solve(int N) {
	srand(time(0));
	vector<int> l, r;
	vector<int> perm(2 * N);
	iota(perm.begin(), perm.end(), 1);
	random_shuffle(perm.begin(), perm.end());
	for(auto &i : perm){
		int v = Query(i);
		if(v != l.size()){
			l.push_back(i);
		}
		else{
			r.push_back(i);
		}
	}
	dnc(l, r, 1);
}

Compilation message (stderr)

minerals.cpp: In function 'void dnc(std::vector<int>, std::vector<int>, int)':
minerals.cpp:18:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=m; i<l.size(); i++){
               ~^~~~~~~~~
minerals.cpp:21:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<r.size(); i++){
               ~^~~~~~~~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:50:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(v != l.size()){
      ~~^~~~~~~~~~~

• 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