oj.uz

Submission #959766

# Submission time Handle Problem Language Result Execution time Memory
959766 2024-04-09T04:02:15 Z josanneo22 The Collection Game (BOI21_swaps) C++17
20 / 100
 36 ms 1436 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) {
	if (N == 1) {
		answer({ 1 });
		return;
	}
	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 27 ms 344 KB Correct
3 Correct 8 ms 440 KB Correct
4 Correct 17 ms 444 KB Correct
5 Correct 8 ms 444 KB Correct
6 Correct 11 ms 444 KB Correct
7 Correct 19 ms 688 KB Correct
8 Correct 16 ms 440 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 20 ms 344 KB Correct
3 Correct 7 ms 440 KB Correct
4 Correct 22 ms 448 KB Correct
5 Correct 9 ms 440 KB Correct
6 Correct 11 ms 440 KB Correct
7 Correct 19 ms 444 KB Correct
8 Correct 22 ms 680 KB Correct
9 Correct 31 ms 1200 KB Correct
10 Correct 31 ms 1436 KB Correct
11 Correct 36 ms 1176 KB Correct
12 Correct 31 ms 1192 KB Correct
13 Correct 31 ms 1188 KB Correct

Subtask #3-1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 22 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 22 ms 344 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 20 ms 344 KB Correct

Subtask #4-1
0 / 9.0

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

Subtask #4-2
0 / 6.0

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

Subtask #5-1
0 / 9.0

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

Subtask #5-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 22 ms 344 KB Correct
3 Incorrect 4 ms 344 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 23 ms 344 KB Correct
3 Incorrect 4 ms 448 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 23 ms 344 KB Correct
3 Incorrect 4 ms 448 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #7-1
0 / 9.0

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

Subtask #7-2
0 / 6.0

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