oj.uz

Submission #805975

# Submission time Handle Problem Language Result Execution time Memory
805975 2023-08-04T04:04:24 Z MetalPower Broken Device (JOI17_broken_device) C++14
100 / 100
 33 ms 2672 KB 
#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);
		}
	}
}

#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2496 KB Output is correct - L* = 40
2 Correct 27 ms 2608 KB Output is correct - L* = 40
3 Correct 33 ms 2608 KB Output is correct - L* = 40
4 Correct 24 ms 2500 KB Output is correct - L* = 40
5 Correct 23 ms 2556 KB Output is correct - L* = 40
6 Correct 26 ms 2500 KB Output is correct - L* = 40
7 Correct 24 ms 2568 KB Output is correct - L* = 40
8 Correct 24 ms 2536 KB Output is correct - L* = 40
9 Correct 26 ms 2500 KB Output is correct - L* = 40
10 Correct 24 ms 2640 KB Output is correct - L* = 40
11 Correct 24 ms 2516 KB Output is correct - L* = 40
12 Correct 24 ms 2584 KB Output is correct - L* = 40
13 Correct 23 ms 2512 KB Output is correct - L* = 40
14 Correct 24 ms 2560 KB Output is correct - L* = 40
15 Correct 25 ms 2624 KB Output is correct - L* = 40
16 Correct 23 ms 2484 KB Output is correct - L* = 40
17 Correct 23 ms 2604 KB Output is correct - L* = 40
18 Correct 24 ms 2632 KB Output is correct - L* = 40
19 Correct 24 ms 2568 KB Output is correct - L* = 40
20 Correct 24 ms 2536 KB Output is correct - L* = 40
21 Correct 24 ms 2548 KB Output is correct - L* = 40
22 Correct 25 ms 2672 KB Output is correct - L* = 40
23 Correct 23 ms 2588 KB Output is correct - L* = 40
24 Correct 23 ms 2536 KB Output is correct - L* = 40
25 Correct 24 ms 2476 KB Output is correct - L* = 40
26 Correct 24 ms 2572 KB Output is correct - L* = 40
27 Correct 24 ms 2484 KB Output is correct - L* = 40
28 Correct 25 ms 2556 KB Output is correct - L* = 40
29 Correct 24 ms 2532 KB Output is correct - L* = 40
30 Correct 23 ms 2556 KB Output is correct - L* = 40
31 Correct 23 ms 2472 KB Output is correct - L* = 40
32 Correct 23 ms 2604 KB Output is correct - L* = 40
33 Correct 23 ms 2520 KB Output is correct - L* = 40
34 Correct 25 ms 2620 KB Output is correct - L* = 40
35 Correct 25 ms 2548 KB Output is correct - L* = 40
36 Correct 24 ms 2484 KB Output is correct - L* = 40
37 Correct 25 ms 2484 KB Output is correct - L* = 40
38 Correct 24 ms 2588 KB Output is correct - L* = 40
39 Correct 25 ms 2604 KB Output is correct - L* = 40
40 Correct 28 ms 2556 KB Output is correct - L* = 40