Submission #376725

#	Time	Username	Problem	Language	Result	Execution time	Memory
376725		Kevin_Zhang_TW	Minerals (JOI19_minerals)	C++17	40 / 100	53 ms	3204 KiB

minerals

#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "minerals.h"

random_device rd;
mt19937 gen(rd());

// Query(int index) ;
// Answer(int A, int B) ;

int qry(int ind) { return Query(ind); }
void ans(int a, int b) { Answer(a, b); }

void dc(vector<int> ids) {
	if (ids.empty()) return;
	shuffle(AI(ids), gen);
	if (ids.size() == 2) {
		ans(ids[0], ids[1]);
		return;
	}
	int n = ids.size(), m = n / 2;

	debug(AI(ids));




	vector<int> stay(n), thd;

	auto check = [&](int l, int r) {

		int lst = 0;
		for (int i = l;i < r;++i) {
			int now = qry(ids[i]);
			if (now == lst) stay[i] = true;
			lst = now;
		}
		for (int i = l;i < r;++i) {
			int now = qry(ids[i]);
			if (now == lst) stay[i] = true;
			lst = now;
		}
		vector<int> old;
		for (int i = l;i < r;++i) {
			if (stay[i]) old.pb(ids[i]);
			else thd.pb(ids[i]);
		}
		dc(old);
	};

	check(0, m), check(m, n);
	dc(thd);

}
void Solve(int N) {
	vector<int> ids(N+N); iota(AI(ids), 1);
	dc(ids);
}

Compilation message (stderr)

minerals.cpp: In function 'void dc(std::vector<int>)':
minerals.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
minerals.cpp:37:2: note: in expansion of macro 'debug'
   37 |  debug(AI(ids));
      |  ^~~~~

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