Submission #376759

#	Time	Username	Problem	Language	Result	Execution time	Memory
376759		Kevin_Zhang_TW	Minerals (JOI19_minerals)	C++17	40 / 100	73 ms	4512 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 cnt ;
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();

	debug(AI(ids));

	vector<int> stay(n), thd;
	vector<vector<int>> thing;

	auto check = [&](int l, int r) {
		chmin(r, n);
		chmin(l, n);
		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]);
		}
		thing.pb(old);
	};

	int len = max(1, n / 3);


	//check(0, m), check(m, n);

	check(0, len + len);

	for (int i = len + len;i < n;++i)
		thd.pb(ids[i]);

	thing.pb(thd);


	DE(n, thing[0].size(), thing[1].size());

	for (auto vec : thing)
		dc(vec);

}
void Solve(int N) {
	vector<int> ids(N+N); iota(AI(ids), 1);
//	DE(2 * (N*2) * __lg(N*2));
//	return;
	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:38:2: note: in expansion of macro 'debug'
   38 |  debug(AI(ids));
      |  ^~~~~
minerals.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
minerals.cpp:78:2: note: in expansion of macro 'DE'
   78 |  DE(n, thing[0].size(), thing[1].size());
      |  ^~

• 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