oj.uz

Submission #837252

# Submission time Handle Problem Language Result Execution time Memory
837252 2023-08-25T08:38:24 Z TranGiaHuy1508 Broken Device (JOI17_broken_device) C++17
95 / 100
 38 ms 2520 KB 
#include <bits/stdc++.h>
using namespace std;

#include "Annalib.h"

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;

namespace {
	ll SEED = 123456789;
	mt19937_64 rng(SEED);

	bool init = false;
	vector<vvi> mapping;

	void generate(){
		if (init) return;
		init = true;

		vvi M = {{1, 6}, {2, 5}, {3, 4}, {7}};
		for (int i = 0; i < 50; i++){
			vvi _M = M;
			shuffle(_M.begin(), _M.end(), rng);
			mapping.push_back(_M);
		}
	}
}

void Anna(int N, ll X, int K, int P[]){
	generate();

	vector<int> broken(N, 0);
	for (int i = 0; i < K; i++) broken[P[i]] = 1;

	// cout << "Anna: ";
	for (int i = 0; i < N; i += 3){
		vector<int> S(3);
		iota(S.begin(), S.end(), i);

		int valid = 7;
		for (int j = 0; j < 3; j++){
			if (broken[S[j]]) valid ^= (1 << j);
		}

		int ed = X & 3;
		int R = 0;
		for (auto mask: mapping[i/3][ed]){
			if ((valid & mask) == mask) R = mask;
		}

		for (int j = 0; j < 3; j++){
			Set(S[j], (R >> j) & 1);
			// cout << ((R >> j) & 1);
		}

		if (R > 0) X >>= 2;
	}
	// cout << "\n";
}
#include <bits/stdc++.h>
using namespace std;

#include "Brunolib.h"

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;

namespace {
	ll SEED = 123456789;
	mt19937_64 rng(SEED);

	bool init = false;
	vector<vvi> mapping;

	void generate(){
		if (init) return;
		init = true;

		vvi M = {{1, 6}, {2, 5}, {3, 4}, {7}};
		for (int i = 0; i < 50; i++){
			vvi _M = M;
			shuffle(_M.begin(), _M.end(), rng);
			mapping.push_back(_M);
		}
	}
}

ll Bruno(int N, int A[]){
	generate();

	ll answer = 0;
	for (int i = N-3; i >= 0; i -= 3){
		vector<int> S(3);
		iota(S.begin(), S.end(), i);

		int repr = 0;
		for (int j = 0; j < 3; j++){
			repr += (A[S[j]] << j);
		}

		int value = -1;
		for (int j = 0; j < 4; j++){
			for (auto k: mapping[i/3][j]){
				if (repr == k) value = j;
			}
		}

		if (value >= 0) answer = (answer << 2) + value;
	}

	// cout << "Bruno: " << answer << "\n";
	return answer;
}

Subtask #1
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2292 KB Output is correct - L* = 40
2 Correct 32 ms 2508 KB Output is correct - L* = 40
3 Partially correct 28 ms 2492 KB Output is partially correct - L* = 39
4 Correct 28 ms 2496 KB Output is correct - L* = 40
5 Correct 28 ms 2376 KB Output is correct - L* = 40
6 Correct 28 ms 2420 KB Output is correct - L* = 40
7 Correct 28 ms 2504 KB Output is correct - L* = 40
8 Correct 32 ms 2404 KB Output is correct - L* = 40
9 Correct 28 ms 2280 KB Output is correct - L* = 40
10 Correct 29 ms 2360 KB Output is correct - L* = 40
11 Correct 37 ms 2320 KB Output is correct - L* = 40
12 Correct 38 ms 2404 KB Output is correct - L* = 40
13 Correct 31 ms 2488 KB Output is correct - L* = 40
14 Correct 28 ms 2356 KB Output is correct - L* = 40
15 Correct 28 ms 2372 KB Output is correct - L* = 40
16 Correct 28 ms 2452 KB Output is correct - L* = 40
17 Correct 30 ms 2448 KB Output is correct - L* = 40
18 Correct 29 ms 2380 KB Output is correct - L* = 40
19 Correct 28 ms 2348 KB Output is correct - L* = 40
20 Correct 28 ms 2408 KB Output is correct - L* = 40
21 Correct 28 ms 2428 KB Output is correct - L* = 40
22 Correct 28 ms 2504 KB Output is correct - L* = 40
23 Correct 27 ms 2412 KB Output is correct - L* = 40
24 Correct 28 ms 2452 KB Output is correct - L* = 40
25 Correct 28 ms 2352 KB Output is correct - L* = 40
26 Correct 28 ms 2500 KB Output is correct - L* = 40
27 Correct 28 ms 2392 KB Output is correct - L* = 40
28 Correct 28 ms 2436 KB Output is correct - L* = 40
29 Correct 28 ms 2420 KB Output is correct - L* = 40
30 Correct 28 ms 2452 KB Output is correct - L* = 40
31 Correct 32 ms 2520 KB Output is correct - L* = 40
32 Correct 31 ms 2484 KB Output is correct - L* = 40
33 Correct 28 ms 2360 KB Output is correct - L* = 40
34 Correct 29 ms 2504 KB Output is correct - L* = 40
35 Correct 28 ms 2444 KB Output is correct - L* = 40
36 Correct 28 ms 2408 KB Output is correct - L* = 40
37 Correct 28 ms 2452 KB Output is correct - L* = 40
38 Correct 29 ms 2392 KB Output is correct - L* = 40
39 Correct 28 ms 2492 KB Output is correct - L* = 40
40 Correct 28 ms 2492 KB Output is correct - L* = 40