oj.uz

Submission #776034

# Submission time Handle Problem Language Result Execution time Memory
776034 2023-07-07T08:50:28 Z 박영우(#9993) The Collection Game (BOI21_swaps) C++17
0 / 100
 13 ms 2960 KB 
#include <bits/stdc++.h>
#include "swaps.h"
using namespace std;
typedef pair<int, int> pii;

#define MAX 101010

int ans[MAX];
vector<pii> qv[MAX];

void simulate(int V) {
	int i;
	for (i = 1; i <= V; i++) {
		if (qv[i].empty()) continue;
		for (auto& [a, b] : qv[i]) schedule(ans[a], ans[b]);
		auto res = visit();
		int p = 0;
		for (auto& [a, b] : qv[i]) if (!res[p++]) swap(ans[a], ans[b]);
	}
}

void solve(int N, int V) {
	int i;
	for (i = 1; i <= N; i++) ans[i] = i;
	int K = 9;
	int cnt = 0;
	int T = 0;
	for (T = 0; T < 10; T++) {
		for (int k = 0; k < K; k++) {
			int d = 1 << k;
			cnt++;
			for (i = 1; i <= N; i++) if (i >> k & 1 && (i - d) > 0) qv[cnt].emplace_back(i - d, i);
			cnt++;
			for (i = 1; i <= N; i++) if (!(i >> k & 1) && (i - d) > 0) qv[cnt].emplace_back(i - d, i);
		}
		for (int k = K - 1; k >= 0; k--) {
			int d = 1 << k;
			cnt++;
			for (i = 1; i <= N; i++) if (i >> k & 1 && (i - d) > 0) qv[cnt].emplace_back(i - d, i);
			cnt++;
			for (i = 1; i <= N; i++) if (!(i >> k & 1) && (i - d) > 0) qv[cnt].emplace_back(i - d, i);
		}
	}

	simulate(cnt);
	vector<int> ansv;
	for (i = 1; i <= N; i++) ansv.push_back(ans[i]);
	answer(ansv);
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2640 KB Correct
2 Correct 7 ms 2768 KB Correct
3 Incorrect 11 ms 2960 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Correct
2 Correct 6 ms 2768 KB Correct
3 Incorrect 13 ms 2896 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #3-1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Correct
2 Incorrect 7 ms 2768 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Correct
2 Incorrect 7 ms 2768 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2640 KB Correct
2 Incorrect 6 ms 2768 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2640 KB Correct
2 Incorrect 6 ms 2768 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #5-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2640 KB Correct
2 Incorrect 6 ms 2768 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2640 KB Correct
2 Incorrect 6 ms 2768 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #6-1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Correct
2 Incorrect 8 ms 2812 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Correct
2 Incorrect 8 ms 2812 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #7-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Correct
2 Incorrect 7 ms 2768 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #7-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Correct
2 Incorrect 7 ms 2768 KB Not correct
3 Halted 0 ms 0 KB -