Submission #113888

#	Time	Username	Problem	Language	Result	Execution time	Memory
113888		Mamnoon_Siam	Minerals (JOI19_minerals)	C++17	100 / 100	804 ms	4984 KiB

minerals

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 43000 + 5;
int dp[maxn], opt[maxn];

void solve(vector<int> u, vector<int> v, int f) {
	if(u.empty()) return;
	if(u.size() == 1) {
		Answer(u.back(), v.back());
		return;
	}

	int mid, last;
	if(f) {
		mid = u.size() - opt[u.size()];
		for(int i = mid; i < v.size(); i++) {
			last = Query(v[i]);
		}
	} else {
		mid = opt[u.size()];
		for(int i = 0; i < mid; i++) {
			last = Query(v[i]);
		}
	}

	vector<int> lu, lv(v.begin(), v.begin() + mid);
	vector<int> ru, rv(v.begin() + mid, v.end());

	for(int i = 0; i < u.size(); i++) {
		if(lu.size() == lv.size()) {			// <
			ru.emplace_back(u[i]);				// <  This part reduces Query()
		} else if(ru.size() == rv.size()) {		// <  call by at least N - 1
			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;
		}
	}

	solve(lu, lv, 1);
	solve(ru, rv, 0);
}

void split(vector<int> v) {
	vector<int> l, r;
	int last = -1;
	for(int i = 0; i < v.size(); i++) {
		if(r.size() == v.size() / 2) { 	// <  This part reduces Query()
			l.emplace_back(v[i]);		// <  call by at least 1
		} else {
			int rep = Query(v[i]);
			if(rep == last) {
				l.emplace_back(v[i]);
			} else {
				r.emplace_back(v[i]);
			} last = rep;
		}
	}
	solve(l, r, 1);
}

void Solve(int N) {
	dp[1] = 0;
	for(int i = 2; i <= N; i++) {
		int mn = INT_MAX, tmp, arg, cmp = (i - 1) / 2 + 1;
		for(int j = 1; j < i; j++) {
			tmp = dp[j] + dp[i - j] + (j < cmp ? j : i - j);
			if(tmp < mn) {
				mn = tmp;
				arg = j;
			}
		}
		dp[i] = mn + i - 1;
		opt[i] = arg;
	}
	/* In worst case scenario, maximum number
	   of calls to Query() is dp[N] + 2N - 1. */
	vector<int> v(2 * N);
	iota(v.begin(), v.end(), 1);
	split(v);
}

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, int)':
minerals.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = mid; i < v.size(); i++) {
                    ~~^~~~~~~~~~
minerals.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < u.size(); i++) {
                 ~~^~~~~~~~~~
minerals.cpp: In function 'void split(std::vector<int>)':
minerals.cpp:55:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, int)':
minerals.cpp:39:4: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(rep == last) {
    ^~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:82:10: warning: 'arg' may be used uninitialized in this function [-Wmaybe-uninitialized]
   opt[i] = arg;
   ~~~~~~~^~~~~

• 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