Submission #547127

#	Time	Username	Problem	Language	Result	Execution time	Memory
547127		benson1029	Minerals (JOI19_minerals)	C++14	100 / 100	69 ms	4040 KiB

minerals

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

bool inside[1000005];
int past = 0;

void solve(vector<int> a, vector<int> b, int t) {
	if(a.size() == 1) {
		Answer(a[0], b[0]);
	} else {
		int sz;
		if(t==0) sz = 0.381966*a.size();
		else sz = (1-0.381966)*a.size();
		if(sz==0) sz++;
		if(sz==a.size()) sz--;
		random_shuffle(b.begin(), b.end());
		vector<int> a1, a2, b1, b2;
		for(int i=0; i<sz; i++) {
			if(!inside[a[i]]) {
				inside[a[i]] = !inside[a[i]];
				past = Query(a[i]);
			}
			a1.push_back(a[i]);
		}
		for(int i=sz; i<a.size(); i++) {
			if(inside[a[i]]) {
				inside[a[i]] = !inside[a[i]];
				past = Query(a[i]);
			}
			a2.push_back(a[i]);
		}
		for(int i=0; i<b.size(); i++) {
			if(b1.size() == a1.size()) {
				b2.push_back(b[i]);
			} else if(b2.size() == a2.size()) {
				b1.push_back(b[i]);
			} else {
				int curr;
				inside[b[i]] = !inside[b[i]];
				curr = Query(b[i]);
				if(curr == past) {
					b1.push_back(b[i]);
				} else {
					b2.push_back(b[i]);
				}
				past = curr;
			}
		}
		solve(a1, b1, 1);
		solve(a2, b2, 0);
	}
}

vector<int> t1,t2;

void Solve(int N) {
	// TODO: Implement your solution here
	for(int i=1; i<=2*N; i++) {
		inside[i] = !inside[i];
		int curr = Query(i);
		if(curr == past) t2.push_back(i);
		else t1.push_back(i);
		past = curr;
	}
	solve(t1, t2, 1);
}

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, int)':
minerals.cpp:16:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   if(sz==a.size()) sz--;
      |      ~~^~~~~~~~~~
minerals.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i=sz; i<a.size(); i++) {
      |                 ~^~~~~~~~~
minerals.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int i=0; i<b.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