oj.uz

Submission #959764

# Submission time Handle Problem Language Result Execution time Memory
959764 2024-04-09T04:00:15 Z josanneo22 The Collection Game (BOI21_swaps) C++17
20 / 100
 35 ms 1684 KB 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define rep(i, n) L(i, 1, n)
#define all(x) x.begin(),x.end()
#define me(x,a) memset(x,a,sizeof(x))

#include<random>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      
#include "swaps.h"

const int nax = 505;
int a[nax];

void N2(int N, int V) {
	L(i, 1, N) a[i] = i;
	L(i, 1, N) L(j, i + 1, N) {
		schedule(a[i], a[j]);
		vector<int> res = visit();
		if (res[0] == 0) swap(a[i], a[j]);
	}
	vector<int> ans;
	L(i, 1, N) ans.push_back(a[i]);
	answer(ans);
	return;
}

void merge(int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	merge(l, mid); merge(mid + 1, r);
	int LP = l, RP = mid + 1;
	vector<int> T;
	while (1) {
		if (LP <= mid && RP <= r) {
			schedule(a[LP], a[RP]);
			vector<int> res = visit();
			if (res[0] == 1) {
				T.push_back(a[LP]);
				LP++;
			}
			else {
				T.push_back(a[RP]);
				RP++;
			}
		}
		else if (LP == mid + 1 && RP <= r) {
			T.push_back(a[RP]);
			RP++;
		}
		else if (LP <= mid && RP == r + 1) {
			T.push_back(a[LP]);
			LP++;
		}
		if (LP == mid + 1 && RP == r + 1) break;
	}
	L(i, l, r) a[i] = T[i - l];
}
void merge_sol(int N, int V) {
	L(i, 1, N) a[i] = i;
	merge(1, N);
	vector<int> ans;
	L(i, 1, N) ans.push_back(a[i]);
	answer(ans);
	return;
}
void odd_even(int N,int V) {
	L(i, 1, N) a[i] = i;
	int par = 0;
	for (int t = 0; t < N; t++) {
		int st = 1 + (par == 1);
		vector<pair<int,int>> q;
		for (int i = st; i + 1 <= N; i += 2) {
			schedule(a[i], a[i + 1]);
			q.push_back(make_pair(i, i + 1));
		}
		vector<int> res = visit();
		for (int i = 0; i < (int)res.size(); i++) {
			if (res[i] == 0) {
				swap(a[q[i].first], a[q[i].second]);
			}
		}
		par ^= 1;
	}
	vector<int> ans;
	L(i, 1, N) ans.push_back(a[i]);
	answer(ans);
	return;
}
void solve(int N, int V) {
	int costN_2 = 0;
	L(i, 1, N) L(j, i + 1, N) costN_2++;
	if (costN_2 <= V) N2(N, V);
	if (N <= 500 && N * 9 <= V) merge_sol(N, V);
	odd_even(N, V);
	return;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 21 ms 344 KB Correct
3 Correct 7 ms 756 KB Correct
4 Correct 21 ms 436 KB Correct
5 Correct 9 ms 448 KB Correct
6 Correct 15 ms 448 KB Correct
7 Correct 27 ms 432 KB Correct
8 Correct 20 ms 440 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 23 ms 344 KB Correct
3 Correct 8 ms 448 KB Correct
4 Correct 16 ms 444 KB Correct
5 Correct 11 ms 444 KB Correct
6 Correct 10 ms 848 KB Correct
7 Correct 20 ms 444 KB Correct
8 Correct 19 ms 436 KB Correct
9 Correct 35 ms 1424 KB Correct
10 Correct 32 ms 1176 KB Correct
11 Correct 31 ms 952 KB Correct
12 Correct 33 ms 932 KB Correct
13 Correct 34 ms 1684 KB Correct

Subtask #3-1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 23 ms 344 KB Correct

Subtask #3-2
2.0 / 2.0

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

Subtask #4-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 25 ms 344 KB Correct
3 Incorrect 5 ms 440 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #4-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 25 ms 344 KB Correct
3 Incorrect 5 ms 440 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #5-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 23 ms 344 KB Correct
3 Incorrect 6 ms 448 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #5-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 23 ms 344 KB Correct
3 Incorrect 6 ms 448 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #6-1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 25 ms 344 KB Correct
3 Incorrect 4 ms 600 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #6-2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 25 ms 344 KB Correct
3 Incorrect 4 ms 600 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #7-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 24 ms 344 KB Correct
3 Incorrect 5 ms 448 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #7-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 24 ms 344 KB Correct
3 Incorrect 5 ms 448 KB Not correct
4 Halted 0 ms 0 KB -