Submission #417931

#	Time	Username	Problem	Language	Result	Execution time	Memory
417931		Kevin_Zhang_TW	The Collection Game (BOI21_swaps)	C++17	0 / 100	1 ms	200 KiB

swaps

#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 "swaps.h"

const int MAX_N = 300010;

void solve(int N, int V) {

	int sz = 1;
	while (sz < N) sz <<= 1;
	vector<int> id(sz); iota(AI(id), 1);

	random_shuffle(AI(id));
	random_shuffle(AI(id));

	vector<pair<int,int>> comp, ext;

	auto add_cp = [&](int i, int j) {
		if (max(id[i], id[j]) > N) {
			ext.pb(i, j);
			return;
		}
		schedule(id[i], id[j]);
		comp.pb(i, j);
	};

	auto done = [&]() {
		vector<int> ret = visit();
		for (int j = 0;j < ret.size();++j) {
			if (ret[j] == 0) {
				auto [x, y] = comp[j];
				DE(id[x], id[y]);
				swap(id[x], id[y]);
			}
		}
		for (auto [i, j] : ext) {
			if (id[i] > N) {
				swap(id[i], id[j]);
			}
		}
		ext.clear();
		comp.clear();
	};

	for (int d = sz/2;d > 0;d >>= 1) {
		for (int i = 0;i < sz;++i) if (i&d)
			add_cp(i-d, i);
		done();
		DE(d);
		debug(AI(id));
	}
	DE("sort back");
	for (int d = 2;d <= sz;d <<= 1) {
		for (int i = 0;i < sz;i += d) {
			for (int j = 1;j < d/2;++j) {
				DE(i+j, i+d/2+j-1);
				add_cp(i+j, i+d/2+j-1);
			}
		}
		done();
		for (int i = 0;i < sz;i += d) {
			vector<int> nod {id[i]};
			for (int j = 1;j < d/2;++j) {
				nod.pb(id[i+j]);
				nod.pb(id[i+d/2+j-1]);
			}
			nod.pb(id[i+d-1]);
			for (int j = 0;j < d;++j)
				id[i + j] = nod[j];
		}
		DE(d);
		debug(AI(id));
	}

	id.resize(N);
	answer(id);
}

Compilation message (stderr)

swaps.cpp: In lambda function:
swaps.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int j = 0;j < ret.size();++j) {
      |                  ~~^~~~~~~~~~~~
swaps.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
swaps.cpp:46:5: note: in expansion of macro 'DE'
   46 |     DE(id[x], id[y]);
      |     ^~
swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
swaps.cpp:63:3: note: in expansion of macro 'DE'
   63 |   DE(d);
      |   ^~
swaps.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
swaps.cpp:64:3: note: in expansion of macro 'debug'
   64 |   debug(AI(id));
      |   ^~~~~
swaps.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
swaps.cpp:66:2: note: in expansion of macro 'DE'
   66 |  DE("sort back");
      |  ^~
swaps.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
swaps.cpp:70:5: note: in expansion of macro 'DE'
   70 |     DE(i+j, i+d/2+j-1);
      |     ^~
swaps.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
swaps.cpp:85:3: note: in expansion of macro 'DE'
   85 |   DE(d);
      |   ^~
swaps.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
swaps.cpp:86:3: note: in expansion of macro 'debug'
   86 |   debug(AI(id));
      |   ^~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 3
• Subtask 4: 0 / 2
• Subtask 5: 0 / 9
• Subtask 6: 0 / 6
• Subtask 7: 0 / 9
• Subtask 8: 0 / 6
• Subtask 9: 0 / 21
• Subtask 10: 0 / 14
• Subtask 11: 0 / 9
• Subtask 12: 0 / 6