제출 #420061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420061		Kevin_Zhang_TW	Broken Device (JOI17_broken_device)	C++17	85 / 100	51 ms	2620 KiB

Anna

#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);
}

Bruno

#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 / 100