Submission #502729

#	Time	Username	Problem	Language	Result	Execution time	Memory
502729		sidon	Minerals (JOI19_minerals)	C++17	100 / 100	37 ms	2876 KiB

minerals

#include "minerals.h"
#include <vector>
 
int A[43000], L, R = -1, last;
 
void dfs(int l, int r, auto b, bool on) {
	if(r - l < 1) return;
	if(r - l < 2) return Answer(A[l], b[0]);
 
	int m = (l + r) / 2;
	if(l < m-1 && m - l == r - m) --m;
	while(__builtin_popcount(m-l) > 2) --m;
 
	for(int i = l; i < m; ++i) last = Query(A[i]);
 
	std::vector<int> bL, bR;
 
	for(int &i : b) {
		int prev = last;
		(size(bR) == r - m || (size(bL) != m - l && (prev == (last = Query(i))) ^ on) ? bL : bR).push_back(i);
	}
	dfs(l, m, bL, on ^ 1);
	dfs(m, r, bR, on);
}
 
void Solve(int N) {
	std::vector<int> b;
	for(int i = 1; i <= N+N; ++i) 
		if(R == N - 1 || Query(i) < R + 2) b.push_back(i);
		else A[++R] = i;
	dfs(0, N, b, 1);
}

Compilation message (stderr)

minerals.cpp:6:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    6 | void dfs(int l, int r, auto b, bool on) {
      |                        ^~~~
minerals.cpp: In instantiation of 'void dfs(int, int, auto:1, bool) [with auto:1 = std::vector<int>]':
minerals.cpp:31:16:   required from here
minerals.cpp:20:13: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |   (size(bR) == r - m || (size(bL) != m - l && (prev == (last = Query(i))) ^ on) ? bL : bR).push_back(i);
      |    ~~~~~~~~~^~~~~~~~
minerals.cpp:20:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |   (size(bR) == r - m || (size(bL) != m - l && (prev == (last = Query(i))) ^ on) ? bL : bR).push_back(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