Submission #547125

#	Time	Username	Problem	Language	Result	Execution time	Memory
547125		benson1029	Minerals (JOI19_minerals)	C++14	90 / 100	63 ms	3576 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) {
	if(a.size() == 1) {
		Answer(a[0], b[0]);
	} else {
		random_shuffle(b.begin(), b.end());
		vector<int> a1, a2, b1, b2;
		for(int i=0; i<a.size()/2; i++) {
			if(!inside[a[i]]) {
				inside[a[i]] = !inside[a[i]];
				past = Query(a[i]);
			}
			a1.push_back(a[i]);
		}
		for(int i=a.size()/2; 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);
		solve(a2, b2);
	}
}

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);
}

Compilation message (stderr)

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