Submission #805962

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
805962	2023-08-04T03:42:17 Z	pavement	The Collection Game (BOI21_swaps)	C++17	25 / 100	24 ms	512 KB

swaps

//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
//     swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//
#include "swaps.h"
#include <iostream>
#include <vector>
#include <set>
using namespace std;

#define pb push_back
#define eb emplace_back

using ii = pair<int, int>;

int N, n0;
vector<ii> cmps;

void cmp(int x, int y) {
	if (x >= N || y >= N) return;
	cmps.eb(x, y);
}

void merge(vector<int> v) {
	if (v.size() == 2) {
		cmp(v[0], v[1]);
		return;
	}
	vector<int> even, odd;
	for (int i = 0; i < (int)v.size(); i++) {
		if (i % 2 == 0) even.pb(v[i]);
		else odd.pb(v[i]);
	}
	merge(even);
	merge(odd);
	for (int i = 1; i + 1 < (int)v.size(); i += 2) {
		cmp(v[i], v[i + 1]);
	}
}

void sort(vector<int> v) {
	if (v.size() == 2) {
		cmp(v[0], v[1]);
		return;
	}
	int m = (int)v.size() / 2;
	sort(vector<int>(v.begin(), v.begin() + m));
	sort(vector<int>(v.begin() + m, v.end()));
	merge(v);
}

void solve(int N, int V) {
	::N = N;
	n0 = 1;
	while (n0 < N) {
		n0 <<= 1;
	}
	vector<int> tmp;
	for (int i = 0; i < n0; i++) {
		tmp.pb(i);
	}
	sort(tmp);
	vector<int> Q, x, y;
	set<int> ss;
	for (int i = 1; i <= N; i++) {
		Q.pb(i - 1);
	}
	for (auto [a, b] : cmps) {
		if (ss.find(Q[a] + 1) != ss.end() || ss.find(Q[b] + 1) != ss.end()) {
			auto ret = visit();
			for (int l = 0; l < (int)ret.size(); l++) {
				if (!ret[l]) {
					swap(Q[x[l]], Q[y[l]]);
				}
			}
			x.clear();
			y.clear();
			ss.clear();
		}
		x.pb(a);
		y.pb(b);
		ss.insert(Q[a] + 1);
		ss.insert(Q[b] + 1);
		schedule(Q[a] + 1, Q[b] + 1);
	}
	auto ret = visit();
	for (int l = 0; l < (int)ret.size(); l++) {
		if (!ret[l]) {
			swap(Q[x[l]], Q[y[l]]);
		}
	}
	for (int &i : Q) i++;
	answer(Q);
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	3 ms	208 KB	Correct
3	Correct	11 ms	336 KB	Correct
4	Correct	20 ms	464 KB	Correct
5	Correct	16 ms	464 KB	Correct
6	Correct	15 ms	464 KB	Correct
7	Correct	23 ms	464 KB	Correct
8	Correct	24 ms	464 KB	Correct

Subtask #2
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	4 ms	208 KB	Correct
3	Correct	10 ms	336 KB	Correct
4	Correct	22 ms	464 KB	Correct
5	Correct	17 ms	464 KB	Correct
6	Correct	17 ms	464 KB	Correct
7	Correct	24 ms	464 KB	Correct
8	Correct	20 ms	464 KB	Correct
9	Runtime error	10 ms	508 KB	Execution killed with signal 13
10	Halted	0 ms	0 KB	-

Subtask #3-1
3.0 / 3.0

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

Subtask #3-2
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	4 ms	208 KB	Correct
3	Correct	1 ms	208 KB	Correct
4	Correct	3 ms	208 KB	Correct

Subtask #4-1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	3 ms	208 KB	Correct
3	Correct	10 ms	348 KB	Correct
4	Correct	22 ms	404 KB	Correct

Subtask #4-2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	3 ms	208 KB	Correct
3	Correct	10 ms	348 KB	Correct
4	Correct	22 ms	404 KB	Correct
5	Correct	1 ms	208 KB	Correct
6	Correct	3 ms	208 KB	Correct
7	Correct	11 ms	336 KB	Correct
8	Correct	22 ms	464 KB	Correct
9	Correct	15 ms	464 KB	Correct
10	Correct	21 ms	464 KB	Correct
11	Correct	12 ms	464 KB	Correct
12	Correct	18 ms	464 KB	Correct
13	Correct	1 ms	208 KB	Correct
14	Correct	4 ms	208 KB	Correct
15	Correct	8 ms	336 KB	Correct
16	Correct	18 ms	464 KB	Correct

Subtask #5-1
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	4 ms	208 KB	Correct
3	Correct	10 ms	336 KB	Correct
4	Correct	19 ms	464 KB	Correct
5	Runtime error	6 ms	464 KB	Execution killed with signal 13
6	Halted	0 ms	0 KB	-

Subtask #5-2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Correct
2	Correct	4 ms	208 KB	Correct
3	Correct	10 ms	336 KB	Correct
4	Correct	19 ms	464 KB	Correct
5	Runtime error	6 ms	464 KB	Execution killed with signal 13
6	Halted	0 ms	0 KB	-

Subtask #6-1
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Correct
2	Correct	4 ms	212 KB	Correct
3	Correct	9 ms	336 KB	Correct
4	Correct	24 ms	512 KB	Correct
5	Runtime error	6 ms	420 KB	Execution killed with signal 13
6	Halted	0 ms	0 KB	-

Subtask #6-2
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Correct
2	Correct	4 ms	212 KB	Correct
3	Correct	9 ms	336 KB	Correct
4	Correct	24 ms	512 KB	Correct
5	Runtime error	6 ms	420 KB	Execution killed with signal 13
6	Halted	0 ms	0 KB	-

Subtask #7-1
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Correct
2	Correct	4 ms	208 KB	Correct
3	Correct	8 ms	336 KB	Correct
4	Correct	18 ms	464 KB	Correct
5	Runtime error	5 ms	416 KB	Execution killed with signal 13
6	Halted	0 ms	0 KB	-

Subtask #7-2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Correct
2	Correct	4 ms	208 KB	Correct
3	Correct	8 ms	336 KB	Correct
4	Correct	18 ms	464 KB	Correct
5	Runtime error	5 ms	416 KB	Execution killed with signal 13
6	Halted	0 ms	0 KB	-

Submission #805962

Compilation message