oj.uz

Submission #420061

# Submission time Handle Problem Language Result Execution time Memory
420061 2021-06-08T04:23:38 Z Kevin_Zhang_TW Broken Device (JOI17_broken_device) C++17
85 / 100
 51 ms 2620 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

const int MAX_N = 300010;
#include "Annalib.h"

// 11 means 1
// 10 means 0
void Anna( int N, long long X, int K, int P[] ){
	vector<int> bad(N);
	for (int i = 0;i < K;++i)
		bad[ P[i] ] = true;


	auto try_gen = [&](ll X) {
		vector<int> res(N);

		auto valid = [&](int s, int v) {
			if (v == 0) {
				return !bad[s+1];
			}
			if (v == 1) {
				return !bad[s];
			}
			if (v == 2) {
				return !bad[s] && !bad[s+1];
			}
			assert(false);
		};
		auto go_fill = [&](int s, int v) {
			if (v > 0) res[s] = true;
			if (v != 1) res[s+1] = true;
		};

		int cnt = 0;
		for (int i = 0;i < N;i += 2) {
			int v = X % 3;
			if (valid(i, v)) {
				go_fill(i, v);
				X /= 3;
				if (++cnt == 38) break;
			}
		}
		return res;
	};

//	auto try_gen = [&](ll X, bool flip) {
//
//		vector<int> res(N);
//		vector<int> val(60);
//		for (int i = 0;i < 60;++i)
//			val[i] = X&1, X>>=1;
//
//		if (flip)
//			for (int i = 0;i < 60;i += 2)
//				val[i] ^= 1;
//
//		int cnt = 0;
//		for (int i = 0, j = 0;i < N && j < 60;++i) {
//			if (bad[i]) continue;
//			if (((i&1) == (val[j]&1))) {
//				res[i] = true;
//				++j;
//			}
//		}
//
//		return res;
//	};
//
//
//	auto a = try_gen(X, false);
//	auto b = try_gen(X, true);
//
//	vector<int> res;
//
//	DE(count(AI(a), 1), count(AI(b), 1));
//
//	if (count(AI(a), 1) >= count(AI(b), 1)) {
//		res = a;
//	}
//	else {
//		res = b;
//		for (int i = N-1;i >= 0;--i) if (!bad[i]) {
//			res[i] = true;
//			break;
//		}
//	}
	auto res = try_gen(X);
	for (int i = 0;i < N;++i)
			Set(i, res[i]);

//	debug(AI(res));
	//DE("Send", X);
}

#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)
namespace {
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

const int MAX_N = 300010;
#include "Brunolib.h"

long long Bruno( int N, int A[] ){

	vector<int> bit;

	int state[2][2]{};

	state[0][1] = 0;
	state[1][0] = 1;
	state[1][1] = 2;

	for (int i = 0;i < N;i += 2) {
		if (A[i] || A[i+1]) {
			bit.pb(state[ A[i] ][ A[i+1] ]);
		}
	}

	reverse(AI(bit));

	ll ret = 0;
	for (int i : bit)
		ret = (ret * 3) + i;

	return ret;


//
//	vector<int> bit;
//
//	for (int i = 0, j = 0;i < N;++i) {
//		if (A[i] == 1) {
//			bit.pb(i&1);
//			++j;
//		}
//	}
//
//	if (bit.size() > 60) {
//		DE(bit.size());
//		bit.resize(60);
//		for (int i = 0;i < 60;i += 2)
//			bit[i] ^= 1;
//	}
//
//	reverse(AI(bit));
//
//	ll X = 0;
//
//	for (int i = 0;i < 60;++i)
//		X = (X<<1) + bit[i];
//
//	DE(X);

//	return X;
}

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 46 ms 2508 KB Output is partially correct - L* = 37
2 Partially correct 38 ms 2500 KB Output is partially correct - L* = 37
3 Partially correct 38 ms 2376 KB Output is partially correct - L* = 37
4 Partially correct 39 ms 2408 KB Output is partially correct - L* = 37
5 Partially correct 51 ms 2508 KB Output is partially correct - L* = 37
6 Partially correct 39 ms 2484 KB Output is partially correct - L* = 37
7 Partially correct 39 ms 2536 KB Output is partially correct - L* = 37
8 Partially correct 43 ms 2448 KB Output is partially correct - L* = 37
9 Partially correct 39 ms 2512 KB Output is partially correct - L* = 37
10 Partially correct 47 ms 2452 KB Output is partially correct - L* = 37
11 Partially correct 38 ms 2468 KB Output is partially correct - L* = 37
12 Partially correct 41 ms 2548 KB Output is partially correct - L* = 37
13 Partially correct 38 ms 2404 KB Output is partially correct - L* = 37
14 Partially correct 41 ms 2528 KB Output is partially correct - L* = 37
15 Partially correct 40 ms 2440 KB Output is partially correct - L* = 37
16 Partially correct 38 ms 2584 KB Output is partially correct - L* = 37
17 Partially correct 44 ms 2468 KB Output is partially correct - L* = 37
18 Partially correct 51 ms 2392 KB Output is partially correct - L* = 37
19 Partially correct 38 ms 2516 KB Output is partially correct - L* = 37
20 Partially correct 38 ms 2452 KB Output is partially correct - L* = 37
21 Partially correct 38 ms 2404 KB Output is partially correct - L* = 37
22 Partially correct 38 ms 2620 KB Output is partially correct - L* = 38
23 Partially correct 40 ms 2528 KB Output is partially correct - L* = 37
24 Partially correct 40 ms 2520 KB Output is partially correct - L* = 37
25 Partially correct 38 ms 2468 KB Output is partially correct - L* = 37
26 Partially correct 38 ms 2576 KB Output is partially correct - L* = 37
27 Partially correct 38 ms 2484 KB Output is partially correct - L* = 37
28 Partially correct 40 ms 2484 KB Output is partially correct - L* = 37
29 Partially correct 43 ms 2516 KB Output is partially correct - L* = 37
30 Partially correct 39 ms 2392 KB Output is partially correct - L* = 37
31 Partially correct 41 ms 2452 KB Output is partially correct - L* = 38
32 Partially correct 38 ms 2468 KB Output is partially correct - L* = 37
33 Partially correct 42 ms 2560 KB Output is partially correct - L* = 37
34 Partially correct 40 ms 2484 KB Output is partially correct - L* = 37
35 Partially correct 41 ms 2504 KB Output is partially correct - L* = 37
36 Partially correct 40 ms 2440 KB Output is partially correct - L* = 37
37 Partially correct 39 ms 2572 KB Output is partially correct - L* = 37
38 Partially correct 40 ms 2468 KB Output is partially correct - L* = 37
39 Partially correct 39 ms 2516 KB Output is partially correct - L* = 37
40 Partially correct 41 ms 2540 KB Output is partially correct - L* = 37