oj.uz

Submission #417892

# Submission time Handle Problem Language Result Execution time Memory
417892 2021-06-04T13:12:41 Z Kevin_Zhang_TW The Collection Game (BOI21_swaps) C++17
35 / 100
 95 ms 528 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "swaps.h"

const int MAX_N = 300010;

void solve(int N, int V) {

	vector<int> id(N); iota(AI(id), 1);


//	{
//		vector<pair<int,int>> comp;
//
//
//		vector<int> ret = visit();
//		for (int j = 0;j < ret.size();++j) {
//			if (ret[j] == 0) {
//				auto [x, y] = comp[j];
//				swap(id[x], id[y]);
//			}
//		}
//	}

	chmin(V, 2 * N);

	for (int i = 0;i < V;++i) {
		vector<pair<int,int>> comp;



		if (i % 3 == 0) {
			int mid = (N) / 2;
			for (int i = mid + (N&1);i < N;++i)
				comp.pb(i-mid, i);
		}
		if (i % 3 == 1) {
			for (int j = 0;j+1 < N;j += 2) { 
				schedule(id[j], id[j+1]);
				comp.pb(j, j+1);
			}
		}
		if (i % 3 == 2) {
			for (int j = 1;j+1 < N;j += 2) { 
				schedule(id[j], id[j+1]);
				comp.pb(j, j+1);
			}
		}

		vector<int> ret = visit();
		for (int j = 0;j < ret.size();++j) {
			if (ret[j] == 0) {
				auto [x, y] = comp[j];
				swap(id[x], id[y]);
			}
		}
	}

	answer(id);
}

Compilation message

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (int j = 0;j < ret.size();++j) {
      |                  ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 7 ms 296 KB Correct
3 Correct 24 ms 200 KB Correct
4 Correct 72 ms 300 KB Correct
5 Correct 87 ms 404 KB Correct
6 Correct 73 ms 524 KB Correct
7 Correct 80 ms 384 KB Correct
8 Correct 71 ms 300 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 6 ms 292 KB Correct
3 Correct 23 ms 200 KB Correct
4 Correct 74 ms 400 KB Correct
5 Correct 82 ms 400 KB Correct
6 Correct 71 ms 300 KB Correct
7 Correct 74 ms 364 KB Correct
8 Correct 80 ms 352 KB Correct
9 Correct 72 ms 300 KB Correct
10 Correct 70 ms 300 KB Correct
11 Correct 84 ms 412 KB Correct
12 Correct 76 ms 300 KB Correct
13 Correct 72 ms 296 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 5 ms 328 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 5 ms 328 KB Correct
3 Correct 1 ms 200 KB Correct
4 Correct 7 ms 288 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 7 ms 200 KB Correct
3 Correct 21 ms 200 KB Correct
4 Correct 83 ms 296 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 7 ms 200 KB Correct
3 Correct 21 ms 200 KB Correct
4 Correct 83 ms 296 KB Correct
5 Correct 1 ms 200 KB Correct
6 Correct 7 ms 292 KB Correct
7 Correct 21 ms 200 KB Correct
8 Correct 73 ms 328 KB Correct
9 Correct 75 ms 528 KB Correct
10 Correct 73 ms 292 KB Correct
11 Correct 82 ms 300 KB Correct
12 Correct 81 ms 424 KB Correct
13 Correct 1 ms 200 KB Correct
14 Correct 5 ms 200 KB Correct
15 Correct 22 ms 200 KB Correct
16 Correct 95 ms 300 KB Correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 5 ms 200 KB Correct
3 Correct 26 ms 200 KB Correct
4 Correct 72 ms 300 KB Correct
5 Incorrect 39 ms 356 KB Not correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 5 ms 200 KB Correct
3 Correct 26 ms 200 KB Correct
4 Correct 72 ms 300 KB Correct
5 Incorrect 39 ms 356 KB Not correct

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 6 ms 200 KB Correct
3 Correct 28 ms 200 KB Correct
4 Correct 72 ms 384 KB Correct
5 Incorrect 46 ms 376 KB Not correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 6 ms 200 KB Correct
3 Correct 28 ms 200 KB Correct
4 Correct 72 ms 384 KB Correct
5 Incorrect 46 ms 376 KB Not correct
6 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 6 ms 200 KB Correct
3 Correct 25 ms 200 KB Correct
4 Correct 72 ms 332 KB Correct
5 Incorrect 38 ms 284 KB Not correct
6 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 6 ms 200 KB Correct
3 Correct 25 ms 200 KB Correct
4 Correct 72 ms 332 KB Correct
5 Incorrect 38 ms 284 KB Not correct
6 Halted 0 ms 0 KB -