Submission #805975

#	Time	Username	Problem	Language	Result	Execution time	Memory
805975		MetalPower	Broken Device (JOI17_broken_device)	C++14	100 / 100	33 ms	2672 KiB

Anna

#include "Annalib.h"

#include <bits/stdc++.h>

int cnt[200], del[200];

// if all K is in different 3-bits
	// 2^40 * 4^10 > 10^18
// for each 2 K's in the same 3-bits
	// exp of 2 --
	// exp of 4 ++

void update(int a, int b, int c, int idx){
	Set(idx, a);
	Set(idx + 1, b);
	Set(idx + 2, c);
}

void Anna(int N, long long X, int K, int P[]){
	memset(del, 0, sizeof del);
	memset(cnt, 0, sizeof cnt);
	for(int i = 0; i < K; i++) del[P[i]]++, cnt[P[i] / 3]++;

	long long C = X;
	for(int i = 0; i < N; i += 3){ // split into 3 bits each
		if(cnt[i / 3] == 0){ // Can represent 2 bits
			if(C % 4 == 0) update(1, 1, 1, i);
			else if(C % 4 == 1) update(0, 1, 1, i);
			else if(C % 4 == 2) update(1, 0, 1, i);
			else if(C % 4 == 3) update(0, 1, 0, i);
			C /= 4;
		}else if(cnt[i / 3] == 1){ // Can only represent 1 bit
			if(C % 2 == 0){
				if(del[i + 2]) update(1, 1, 0, i);
				else update(0, 0, 1, i);
				C /= 2;
			}else{
				if(del[i]){
					// switch to 4
					if((C / 2) % 2 == 0) update(0, 1, 1, i);
					else update(0, 1, 0, i);
					C /= 4;
				}else{
					update(1, 0, 0, i);
					C /= 2;
				}
			}
		}else{
			update(0, 0, 0, i);
		}
	}
}

Bruno

#include "Brunolib.h"

long long Bruno(int N, int A[]){
	long long ans = 0, mul = 1;
	for(int i = N - 3; i >= 0; i -= 3){
		int curr = A[i] + 2 * A[i + 1] + 4 * A[i + 2];
		if(curr == 0) continue;
		else if(curr == 1) ans *= 2, ans += 1;
		else if(curr == 2) ans *= 4, ans += 3;
		else if(curr == 3) ans *= 2;
		else if(curr == 4) ans *= 2;
		else if(curr == 5) ans *= 4, ans += 2;
		else if(curr == 6) ans *= 4, ans += 1;
		else if(curr == 7) ans *= 4;
	}
	return ans;
}

Compilation message (stderr)

Bruno.cpp: In function 'long long int Bruno(int, int*)':
Bruno.cpp:4:21: warning: unused variable 'mul' [-Wunused-variable]
    4 |  long long ans = 0, mul = 1;
      |                     ^~~

• Subtask 1: 100 / 100