oj.uz

Submission #660108

# Submission time Handle Problem Language Result Execution time Memory
660108 2022-11-20T11:13:01 Z ymm The Collection Game (BOI21_swaps) C++17
35 / 100
 33 ms 444 KB 
#include "swaps.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int LG = 9;
const int N = 1<<LG;
vector<int> ord;
vector<pii> sched;
int n;

vector<int> cmp()
{
	int cnt = 0;
	for (auto [i, j] : sched) {
		int x = ord[i];
		int y = ord[j];
		if (x > n || y > n)
			continue;
		schedule(x, y);
		++cnt;
	}
	vector<int> res = cnt? visit(): vector<int>(), ans;
	reverse(res.begin(), res.end());
	for (auto [i, j] : sched) {
		int x = ord[i];
		int y = ord[j];
		if (x > n || y > n) {
			ans.push_back(x < y);
		} else {
			ans.push_back(res.back());
			res.pop_back();
		}
	}
	return ans;
}

void Do(int sz)
{
	Loop (x,0,sz) {
		for (int l = 0; l < N; l += 2*sz) {
			int m = l + sz;
			int r = m + sz;
			Loop (i,l+x,m)
				sched.push_back({i, i+sz-x});
		}
		auto res = cmp();
		Loop (k,0,sched.size()) {
			int x = res[k];
			auto [i, j] = sched[k];
			if (!x)
				swap(ord[i], ord[j]);
		}
		sched.clear();
	}
}

void solve(int _n, int v)
{
	n = _n;
	ord.resize(N);
	iota(ord.begin(), ord.end(), 1);
	Loop (i,0,LG)
		Do(1<<i);
	ord.resize(n);
	answer(ord);
}

Compilation message

swaps.cpp: In function 'void Do(int)':
swaps.cpp:47:8: warning: unused variable 'r' [-Wunused-variable]
   47 |    int r = m + sz;
      |        ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 9 ms 208 KB Correct
4 Correct 27 ms 332 KB Correct
5 Correct 23 ms 444 KB Correct
6 Correct 27 ms 440 KB Correct
7 Correct 23 ms 312 KB Correct
8 Correct 22 ms 344 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 9 ms 208 KB Correct
4 Correct 29 ms 324 KB Correct
5 Correct 24 ms 328 KB Correct
6 Correct 31 ms 432 KB Correct
7 Correct 22 ms 332 KB Correct
8 Correct 26 ms 316 KB Correct
9 Correct 24 ms 320 KB Correct
10 Correct 22 ms 392 KB Correct
11 Correct 33 ms 328 KB Correct
12 Correct 27 ms 316 KB Correct
13 Correct 22 ms 312 KB Correct

Subtask #3
3.0 / 3.0

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

Subtask #4
2.0 / 2.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 11 ms 308 KB Correct
4 Correct 25 ms 328 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 11 ms 308 KB Correct
4 Correct 25 ms 328 KB Correct
5 Correct 2 ms 208 KB Correct
6 Correct 4 ms 208 KB Correct
7 Correct 8 ms 208 KB Correct
8 Correct 24 ms 328 KB Correct
9 Correct 25 ms 312 KB Correct
10 Correct 24 ms 420 KB Correct
11 Correct 26 ms 324 KB Correct
12 Correct 23 ms 420 KB Correct
13 Correct 2 ms 208 KB Correct
14 Correct 4 ms 208 KB Correct
15 Correct 10 ms 288 KB Correct
16 Correct 26 ms 316 KB Correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 9 ms 208 KB Correct
4 Correct 24 ms 444 KB Correct
5 Runtime error 25 ms 376 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 9 ms 208 KB Correct
4 Correct 24 ms 444 KB Correct
5 Runtime error 25 ms 376 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct
3 Correct 9 ms 304 KB Correct
4 Correct 23 ms 336 KB Correct
5 Runtime error 33 ms 440 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct
3 Correct 9 ms 304 KB Correct
4 Correct 23 ms 336 KB Correct
5 Runtime error 33 ms 440 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct
3 Correct 8 ms 308 KB Correct
4 Correct 32 ms 324 KB Correct
5 Runtime error 27 ms 392 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct
3 Correct 8 ms 308 KB Correct
4 Correct 32 ms 324 KB Correct
5 Runtime error 27 ms 392 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -