Submission #417892

#	Time	Username	Problem	Language	Result	Execution time	Memory
417892		Kevin_Zhang_TW	The Collection Game (BOI21_swaps)	C++17	35 / 100	95 ms	528 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) {

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


//	{
//		vector<pair<int,int>> comp;
//
//
//		vector<int> ret = visit();
//		for (int j = 0;j < ret.size();++j) {
//			if (ret[j] == 0) {
//				auto [x, y] = comp[j];
//				swap(id[x], id[y]);
//			}
//		}
//	}

	chmin(V, 2 * N);

	for (int i = 0;i < V;++i) {
		vector<pair<int,int>> comp;



		if (i % 3 == 0) {
			int mid = (N) / 2;
			for (int i = mid + (N&1);i < N;++i)
				comp.pb(i-mid, i);
		}
		if (i % 3 == 1) {
			for (int j = 0;j+1 < N;j += 2) { 
				schedule(id[j], id[j+1]);
				comp.pb(j, j+1);
			}
		}
		if (i % 3 == 2) {
			for (int j = 1;j+1 < N;j += 2) { 
				schedule(id[j], id[j+1]);
				comp.pb(j, j+1);
			}
		}

		vector<int> ret = visit();
		for (int j = 0;j < ret.size();++j) {
			if (ret[j] == 0) {
				auto [x, y] = comp[j];
				swap(id[x], id[y]);
			}
		}
	}

	answer(id);
}

Compilation message (stderr)

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (int j = 0;j < ret.size();++j) {
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 9 / 9
• Subtask 6: 6 / 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