oj.uz

Submission #534810

# Submission time Handle Problem Language Result Execution time Memory
534810 2022-03-09T02:47:57 Z skittles1412 The Collection Game (BOI21_swaps) C++17
50 / 100
 483 ms 680 KB 
#include "swaps.h"
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 505;

namespace s1 {

void sch(int a, int b) {
	schedule(a + 1, b + 1);
}

void answ(vector<int> arr) {
	for (auto& a : arr) {
		a++;
	}
	answer(arr);
	exit(0);
}

bool solve(int n, int m) {
	if (m < 1000) {
		return false;
	}
	bool arr[maxn][maxn] {};
	for (int i = 0; i < n; i++) {
		vector<pair<int, int>> vals;
		for (int j = 0; j < n; j++) {
			int x = (n + i - j) % n;
			if (x < j) {
				vals.emplace_back(j, x);
				sch(j, x);
			}
		}
		vector<int> res = visit();
		int rind = 0;
		for (auto& [a, b] : vals) {
			int c = res[rind++];
			arr[a][b] = c;
			arr[b][a] = c ^ 1;
		}
	}
	vector<int> ord(n);
	iota(begin(ord), end(ord), 0);
	sort(begin(ord), end(ord), [&](int a, int b) -> bool {
		if (a == b) {
			return false;
		}
		return arr[a][b];
	});
	answ(ord);
	return true;
}

}

int perm[maxn];
vector<pair<int, int>> queued;

void init() {
	iota(begin(perm), end(perm), 1);
}

void mschedule(int a, int b) {
	queued.emplace_back(a, b);
}

void mvisit() {
	if (!sz(queued)) {
		return;
	}
	for (auto& [a, b] : queued) {
		schedule(perm[a], perm[b]);
	}
	vector<int> res = visit();
	int rind = 0;
	for (auto& [a, b] : queued) {
		if (!res[rind++]) {
			swap(perm[a], perm[b]);
		}
	}
	queued.clear();
}

void manswer(int n) {
	answer(vector<int>(perm, perm + n));
}

namespace s2 {

bool solve(int n, int m) {
	for (int i = 0; i < m; i += 2) {
		for (int j = 1; j + 1 < n; j += 2) {
			mschedule(j, j + 1);
		}
		mvisit();
		for (int j = 0; j + 1 < n; j += 2) {
			mschedule(j, j + 1);
		}
		mvisit();
	}
	manswer(n);
	return true;
}

}

void solve(int n, int m) {
	init();
	s2::solve(n, m);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 200 KB Correct
2 Correct 131 ms 200 KB Correct
3 Correct 256 ms 200 KB Correct
4 Correct 483 ms 432 KB Correct
5 Correct 424 ms 404 KB Correct
6 Correct 426 ms 380 KB Correct
7 Correct 410 ms 360 KB Correct
8 Correct 411 ms 400 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 200 KB Correct
2 Correct 116 ms 200 KB Correct
3 Correct 234 ms 200 KB Correct
4 Correct 422 ms 388 KB Correct
5 Correct 434 ms 424 KB Correct
6 Correct 425 ms 468 KB Correct
7 Correct 423 ms 580 KB Correct
8 Correct 431 ms 424 KB Correct
9 Correct 85 ms 296 KB Correct
10 Correct 82 ms 300 KB Correct
11 Correct 84 ms 384 KB Correct
12 Correct 86 ms 404 KB Correct
13 Correct 97 ms 296 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 200 KB Correct
2 Correct 123 ms 200 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 200 KB Correct
2 Correct 123 ms 200 KB Correct
3 Correct 49 ms 200 KB Correct
4 Correct 135 ms 200 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 200 KB Correct
2 Correct 123 ms 200 KB Correct
3 Correct 227 ms 200 KB Correct
4 Correct 411 ms 512 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 200 KB Correct
2 Correct 123 ms 200 KB Correct
3 Correct 227 ms 200 KB Correct
4 Correct 411 ms 512 KB Correct
5 Correct 56 ms 200 KB Correct
6 Correct 115 ms 200 KB Correct
7 Correct 238 ms 200 KB Correct
8 Correct 419 ms 484 KB Correct
9 Correct 448 ms 472 KB Correct
10 Correct 407 ms 408 KB Correct
11 Correct 436 ms 372 KB Correct
12 Correct 441 ms 460 KB Correct
13 Correct 52 ms 200 KB Correct
14 Correct 121 ms 200 KB Correct
15 Correct 239 ms 200 KB Correct
16 Correct 435 ms 516 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 200 KB Correct
2 Correct 109 ms 200 KB Correct
3 Correct 244 ms 200 KB Correct
4 Correct 420 ms 372 KB Correct
5 Correct 44 ms 288 KB Correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 200 KB Correct
2 Correct 109 ms 200 KB Correct
3 Correct 244 ms 200 KB Correct
4 Correct 420 ms 372 KB Correct
5 Correct 44 ms 288 KB Correct
6 Correct 57 ms 200 KB Correct
7 Correct 114 ms 200 KB Correct
8 Correct 224 ms 200 KB Correct
9 Correct 427 ms 680 KB Correct
10 Correct 432 ms 372 KB Correct
11 Correct 417 ms 456 KB Correct
12 Correct 419 ms 480 KB Correct
13 Correct 449 ms 480 KB Correct
14 Correct 83 ms 524 KB Correct
15 Correct 79 ms 296 KB Correct
16 Correct 87 ms 428 KB Correct
17 Correct 83 ms 376 KB Correct
18 Correct 97 ms 296 KB Correct
19 Correct 56 ms 200 KB Correct
20 Correct 105 ms 200 KB Correct
21 Correct 225 ms 200 KB Correct
22 Correct 460 ms 400 KB Correct
23 Correct 46 ms 296 KB Correct

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 200 KB Correct
2 Correct 128 ms 200 KB Correct
3 Correct 202 ms 200 KB Correct
4 Correct 422 ms 304 KB Correct
5 Correct 44 ms 296 KB Correct
6 Incorrect 8 ms 288 KB Not correct
7 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 200 KB Correct
2 Correct 128 ms 200 KB Correct
3 Correct 202 ms 200 KB Correct
4 Correct 422 ms 304 KB Correct
5 Correct 44 ms 296 KB Correct
6 Incorrect 8 ms 288 KB Not correct
7 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 200 KB Correct
2 Correct 128 ms 200 KB Correct
3 Correct 225 ms 200 KB Correct
4 Correct 428 ms 348 KB Correct
5 Correct 41 ms 380 KB Correct
6 Incorrect 9 ms 288 KB Not correct
7 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 200 KB Correct
2 Correct 128 ms 200 KB Correct
3 Correct 225 ms 200 KB Correct
4 Correct 428 ms 348 KB Correct
5 Correct 41 ms 380 KB Correct
6 Incorrect 9 ms 288 KB Not correct
7 Halted 0 ms 0 KB -