Submission #113870

#	Time	Username	Problem	Language	Result	Execution time	Memory
113870		Mamnoon_Siam	Minerals (JOI19_minerals)	C++17	75 / 100	122 ms	5364 KiB

minerals

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

mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
struct RNG {
	int operator () (int n) {
		return rnd(n);
	}
};

void scattered(vector<int> u, vector<int> v, int f) {
	if(u.empty()) return;

	if(u.size() == 1) {
		Answer(u.back(), v.back());
		return;
	}
	random_shuffle(u.begin(), u.end(), RNG());
	random_shuffle(v.begin(), v.end(), RNG());
	int mid = ((int)u.size() - 2) >> 1;
	int last;
	if(f) {
		for(int i = mid + 1; i < v.size(); i++) {
			last = Query(v[i]);
		}
	} else {
		for(int i = 0; i <= mid; i++) {
			last = Query(v[i]);
		}
	}
	vector<int> lu, lv(v.begin(), v.begin() + mid + 1), ru, rv(v.begin() + mid + 1, v.end());
	for(int i = 0; i < u.size(); i++) {
		if(lu.size() == lv.size()) {
			ru.emplace_back(u[i]);
		} else if(ru.size() == rv.size()) {
			lu.emplace_back(u[i]);
		} else {
			int rep = Query(u[i]);
			if(rep == last) {
				lu.emplace_back(u[i]);
			} else {
				ru.emplace_back(u[i]);
			}
			last = rep;
		}
	}
	scattered(lu, lv, 1);
	scattered(ru, rv, 0);
}

void together(vector<int> v) {
	random_shuffle(v.begin(), v.end(), RNG());

	if(v.empty()) return;
	if(v.size() == 2) return Answer(v[0], v[1]);
	if(v.size() == 4) {
		int last = Query(v[0]);
		if(Query(v[1]) == last) {
			together({v[0], v[1]});
			together({v[2], v[3]});
			return;
		} else {
			scattered({v[2], v[3]}, {v[0], v[1]}, 1);
		}
		return;
	}
	if(v.size() == 6) {
		int last = Query(v[0]), rep;
		rep = Query(v[1]);
		if(rep == last) {
			Answer(v[0], v[1]);
			together({v[2], v[3], v[4], v[5]});
			return;
		} else {
			last = rep;
			rep = Query(v[2]);
			if(rep == last) {
				last = rep;
				rep = Query(v[0]);
				if(rep == last) {
					last = rep;
					Answer(v[0], v[2]);
					if(Query(v[3]) == last) {
						together({v[1], v[3]});
						together({v[4], v[5]});
						return;
					} else {
						return scattered({v[4], v[5]}, {v[1], v[3]}, 1);
					}
				} else {
					Answer(v[1], v[2]);
					return together({v[0], v[3], v[4], v[5]});
				}
			} else {
				return scattered({v[3], v[4], v[5]}, {v[0], v[1], v[2]}, 1);
			}
		}
		return;
	}

	int mid = ((int)v.size()) / 2 - 1;

	vector<int> l, r, dl, dr;
	int last = 0;
	for(int i = 0; i <= mid; i++) {
		int rep = Query(v[i]);
		if(rep == last) {
			l.emplace_back(v[i]);
		}
		last = rep;
	}
	for(int i = 0; i <= mid; i++) {
		int rep = Query(v[i]);
		if(rep == last) {
			l.emplace_back(v[i]);
		}
		last = rep;
	}
	last = 0;
	for(int i = mid + 1; i < v.size(); i++) {
		int rep = Query(v[i]);
		if(rep == last) {
			r.emplace_back(v[i]);
		}
		last = rep;
	}
	for(int i = mid + 1; i < v.size(); i++) {
		int rep = Query(v[i]);
		if(rep == last) {
			r.emplace_back(v[i]);
		}
		last = rep;
	}
	set<int> sl(l.begin(), l.end()), sr(r.begin(), r.end());
	for(int i = 0; i <= mid; i++) {
		if(sl.find(v[i]) == sl.end()) {
			dl.emplace_back(v[i]);
		}
	}
	for(int i = mid + 1; i < v.size(); i++) {
		if(sr.find(v[i]) == sr.end()) {
			dr.emplace_back(v[i]);
		}
	}
	together(l);
	together(r);
	scattered(dl, dr, 0);
}

void Solve(int N) {
	vector<int> v(2 * N);
	iota(v.begin(), v.end(), 1);
	together(v);
}

Compilation message (stderr)

minerals.cpp: In function 'void scattered(std::vector<int>, std::vector<int>, int)':
minerals.cpp:25:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = mid + 1; i < v.size(); i++) {
                        ~~^~~~~~~~~~
minerals.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < u.size(); i++) {
                 ~~^~~~~~~~~~
minerals.cpp: In function 'void together(std::vector<int>)':
minerals.cpp:122:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = mid + 1; i < v.size(); i++) {
                       ~~^~~~~~~~~~
minerals.cpp:129:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = mid + 1; i < v.size(); i++) {
                       ~~^~~~~~~~~~
minerals.cpp:142:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = mid + 1; i < v.size(); i++) {
                       ~~^~~~~~~~~~
minerals.cpp: In function 'void scattered(std::vector<int>, std::vector<int>, int)':
minerals.cpp:41:4: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(rep == last) {
    ^~

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