oj.uz

답안 #805962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
805962 2023-08-04T03:42:17 Z pavement The Collection Game (BOI21_swaps) C++17
25 / 100
 24 ms 512 KB 
//
// --- 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct

Subtask #3-2
2.0 / 2.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -