oj.uz

Submission #837253

# Submission time Handle Problem Language Result Execution time Memory
837253 2023-08-25T08:39:18 Z TranGiaHuy1508 Broken Device (JOI17_broken_device) C++17
85 / 100
 35 ms 2512 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 = 123456790;
	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 = 123456790;
	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
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2332 KB Output is correct - L* = 40
2 Partially correct 28 ms 2512 KB Output is partially correct - L* = 37
3 Correct 28 ms 2364 KB Output is correct - L* = 40
4 Correct 28 ms 2436 KB Output is correct - L* = 40
5 Partially correct 28 ms 2492 KB Output is partially correct - L* = 39
6 Partially correct 27 ms 2464 KB Output is partially correct - L* = 38
7 Partially correct 28 ms 2408 KB Output is partially correct - L* = 39
8 Correct 35 ms 2496 KB Output is correct - L* = 40
9 Partially correct 28 ms 2364 KB Output is partially correct - L* = 37
10 Correct 30 ms 2336 KB Output is correct - L* = 40
11 Partially correct 30 ms 2476 KB Output is partially correct - L* = 38
12 Partially correct 28 ms 2432 KB Output is partially correct - L* = 39
13 Correct 28 ms 2452 KB Output is correct - L* = 40
14 Partially correct 28 ms 2408 KB Output is partially correct - L* = 38
15 Correct 28 ms 2384 KB Output is correct - L* = 40
16 Partially correct 28 ms 2456 KB Output is partially correct - L* = 39
17 Correct 29 ms 2408 KB Output is correct - L* = 40
18 Partially correct 34 ms 2420 KB Output is partially correct - L* = 38
19 Correct 28 ms 2500 KB Output is correct - L* = 40
20 Partially correct 28 ms 2448 KB Output is partially correct - L* = 37
21 Correct 29 ms 2364 KB Output is correct - L* = 40
22 Correct 28 ms 2388 KB Output is correct - L* = 40
23 Correct 30 ms 2468 KB Output is correct - L* = 40
24 Correct 28 ms 2508 KB Output is correct - L* = 40
25 Correct 27 ms 2472 KB Output is correct - L* = 40
26 Partially correct 28 ms 2468 KB Output is partially correct - L* = 38
27 Partially correct 27 ms 2484 KB Output is partially correct - L* = 38
28 Partially correct 28 ms 2504 KB Output is partially correct - L* = 39
29 Partially correct 31 ms 2288 KB Output is partially correct - L* = 39
30 Correct 28 ms 2332 KB Output is correct - L* = 40
31 Correct 30 ms 2372 KB Output is correct - L* = 40
32 Correct 28 ms 2428 KB Output is correct - L* = 40
33 Partially correct 28 ms 2348 KB Output is partially correct - L* = 38
34 Partially correct 28 ms 2480 KB Output is partially correct - L* = 39
35 Correct 28 ms 2512 KB Output is correct - L* = 40
36 Correct 28 ms 2488 KB Output is correct - L* = 40
37 Partially correct 28 ms 2456 KB Output is partially correct - L* = 39
38 Partially correct 28 ms 2448 KB Output is partially correct - L* = 37
39 Partially correct 28 ms 2300 KB Output is partially correct - L* = 38
40 Partially correct 29 ms 2440 KB Output is partially correct - L* = 39