Submission #660115

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
660115	2022-11-20T11:33:33 Z	ymm	The Collection Game (BOI21_swaps)	C++17	50 / 100	516 ms	656 KB

swaps

#include "swaps.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int LG = 9;
const int N = 1<<LG;
vector<int> ord;
vector<pii> sched;
int n;

vector<int> cmp()
{
	int cnt = 0;
	for (auto [i, j] : sched) {
		int x = ord[i];
		int y = ord[j];
		if (x > n || y > n)
			continue;
		schedule(x, y);
		++cnt;
	}
	vector<int> res = cnt? visit(): vector<int>(), ans;
	reverse(res.begin(), res.end());
	for (auto [i, j] : sched) {
		int x = ord[i];
		int y = ord[j];
		if (x > n || y > n) {
			ans.push_back(x < y);
		} else {
			ans.push_back(res.back());
			res.pop_back();
		}
	}
	return ans;
}

void Do(int par)
{
	for (int i = par; i + 2 <= n; i += 2)
		sched.push_back({i, i+1});
	auto res = cmp();
	Loop (k,0,sched.size()) {
		int x = res[k];
		auto [i, j] = sched[k];
		if (!x)
			swap(ord[i], ord[j]);
	}
	sched.clear();
}

void solve(int _n, int v)
{
	n = _n;
	ord.resize(N);
	iota(ord.begin(), ord.end(), 1);
	Loop (i,0,v)
		Do(i&1);
	ord.resize(n);
	answer(ord);
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	208 KB	Correct
2	Correct	98 ms	208 KB	Correct
3	Correct	239 ms	208 KB	Correct
4	Correct	441 ms	488 KB	Correct
5	Correct	486 ms	456 KB	Correct
6	Correct	466 ms	656 KB	Correct
7	Correct	502 ms	408 KB	Correct
8	Correct	455 ms	412 KB	Correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	208 KB	Correct
2	Correct	119 ms	208 KB	Correct
3	Correct	247 ms	208 KB	Correct
4	Correct	483 ms	368 KB	Correct
5	Correct	480 ms	412 KB	Correct
6	Correct	454 ms	348 KB	Correct
7	Correct	516 ms	496 KB	Correct
8	Correct	459 ms	528 KB	Correct
9	Correct	90 ms	308 KB	Correct
10	Correct	90 ms	492 KB	Correct
11	Correct	100 ms	396 KB	Correct
12	Correct	104 ms	308 KB	Correct
13	Correct	105 ms	308 KB	Correct

Subtask #3
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	208 KB	Correct
2	Correct	118 ms	208 KB	Correct

Subtask #4
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	208 KB	Correct
2	Correct	118 ms	208 KB	Correct
3	Correct	63 ms	208 KB	Correct
4	Correct	134 ms	208 KB	Correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	208 KB	Correct
2	Correct	129 ms	208 KB	Correct
3	Correct	224 ms	208 KB	Correct
4	Correct	440 ms	512 KB	Correct

Subtask #6
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	208 KB	Correct
2	Correct	129 ms	208 KB	Correct
3	Correct	224 ms	208 KB	Correct
4	Correct	440 ms	512 KB	Correct
5	Correct	52 ms	208 KB	Correct
6	Correct	116 ms	208 KB	Correct
7	Correct	249 ms	208 KB	Correct
8	Correct	427 ms	372 KB	Correct
9	Correct	450 ms	576 KB	Correct
10	Correct	482 ms	360 KB	Correct
11	Correct	415 ms	536 KB	Correct
12	Correct	465 ms	364 KB	Correct
13	Correct	53 ms	208 KB	Correct
14	Correct	123 ms	208 KB	Correct
15	Correct	237 ms	208 KB	Correct
16	Correct	479 ms	412 KB	Correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	208 KB	Correct
2	Correct	143 ms	208 KB	Correct
3	Correct	230 ms	256 KB	Correct
4	Correct	457 ms	356 KB	Correct
5	Correct	49 ms	296 KB	Correct

Subtask #8
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	208 KB	Correct
2	Correct	143 ms	208 KB	Correct
3	Correct	230 ms	256 KB	Correct
4	Correct	457 ms	356 KB	Correct
5	Correct	49 ms	296 KB	Correct
6	Correct	50 ms	208 KB	Correct
7	Correct	130 ms	208 KB	Correct
8	Correct	240 ms	208 KB	Correct
9	Correct	469 ms	472 KB	Correct
10	Correct	439 ms	420 KB	Correct
11	Correct	424 ms	396 KB	Correct
12	Correct	458 ms	436 KB	Correct
13	Correct	481 ms	456 KB	Correct
14	Correct	99 ms	376 KB	Correct
15	Correct	85 ms	308 KB	Correct
16	Correct	81 ms	308 KB	Correct
17	Correct	91 ms	408 KB	Correct
18	Correct	115 ms	308 KB	Correct
19	Correct	53 ms	208 KB	Correct
20	Correct	129 ms	296 KB	Correct
21	Correct	244 ms	208 KB	Correct
22	Correct	478 ms	408 KB	Correct
23	Correct	48 ms	476 KB	Correct

Subtask #9
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	208 KB	Correct
2	Correct	117 ms	208 KB	Correct
3	Correct	273 ms	208 KB	Correct
4	Correct	468 ms	496 KB	Correct
5	Correct	40 ms	304 KB	Correct
6	Incorrect	9 ms	336 KB	Not correct
7	Halted	0 ms	0 KB	-

Subtask #10
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	208 KB	Correct
2	Correct	117 ms	208 KB	Correct
3	Correct	273 ms	208 KB	Correct
4	Correct	468 ms	496 KB	Correct
5	Correct	40 ms	304 KB	Correct
6	Incorrect	9 ms	336 KB	Not correct
7	Halted	0 ms	0 KB	-

Subtask #11
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	208 KB	Correct
2	Correct	106 ms	208 KB	Correct
3	Correct	239 ms	208 KB	Correct
4	Correct	414 ms	628 KB	Correct
5	Correct	38 ms	308 KB	Correct
6	Incorrect	8 ms	288 KB	Not correct
7	Halted	0 ms	0 KB	-

Subtask #12
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	208 KB	Correct
2	Correct	106 ms	208 KB	Correct
3	Correct	239 ms	208 KB	Correct
4	Correct	414 ms	628 KB	Correct
5	Correct	38 ms	308 KB	Correct
6	Incorrect	8 ms	288 KB	Not correct
7	Halted	0 ms	0 KB	-

Submission #660115

Compilation message