oj.uz

Submission #43815

# Submission time Handle Problem Language Result Execution time Memory
43815 2018-03-24T07:54:50 Z cheater2k Broken Device (JOI17_broken_device) C++14
100 / 100
 60 ms 3808 KB 
#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;

vector <int> mp2[4];
vector <int> mp1[3];
bool broken[155];

int getbit(long long X, int i) {
	if (i <= 62) return (X >> i & 1);
	else return 0;
}

void Anna(int N, long long X, int K, int P[]) {
	mp1[0] = {0, 0, 1}; // 0
	mp1[1] = {0, 1, 1}; // 1
	mp1[2] = {1, 0, 0}; // 1
	mp2[0] = {0, 1, 0}; // 00
	mp2[1] = {1, 0, 1}; // 01
	mp2[2] = {1, 1, 0}; // 10
	mp2[3] = {1, 1, 1}; // 11

	memset(broken, 0, sizeof broken);
  for (int i = 0; i < K; ++i) broken[P[i]] = 1;

  int cur = 0;
  for (int i = 0; i < N; i += 3) {
  	int cnt = broken[i] + broken[i + 1] + broken[i + 2];
  	if (cnt >= 2) {
  		Set(i, 0);
  		Set(i + 1, 0);
  		Set(i + 2, 0);
  	}
  	else if (cnt == 0) {
  		int x = getbit(X, cur) + getbit(X, cur + 1) * 2;
  		Set(i, mp2[x][0]);
  		Set(i + 1, mp2[x][1]);
  		Set(i + 2, mp2[x][2]);
  		cur += 2;
  	}
  	else { // cnt = 1
  		if (getbit(X, cur)) {
  			int x = 2; if (broken[i]) x = 1; 
  			Set(i, mp1[x][0]), Set(i + 1, mp1[x][1]), Set(i + 2, mp1[x][2]);
  			++cur;
  		} else {
  			if (!broken[i + 2]) {
  				Set(i, mp1[0][0]), Set(i + 1, mp1[0][1]), Set(i + 2, mp1[0][2]);
  				++cur;
  			} else { // 00 or 10
  				int x = getbit(X, cur + 1) * 2;
  				Set(i, mp2[x][0]), Set(i + 1, mp2[x][1]), Set(i + 2, mp2[x][2]);
  				cur += 2;
  			}
  		}
  	}
  }
}

#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;

int val[8], bits[8];

long long Bruno(int N, int A[]) {
	val[1] = 0, bits[1] = 1;
	val[2] = 0, bits[2] = 2;
	val[3] = 1, bits[3] = 1;
	val[4] = 1, bits[4] = 1;
	val[5] = 1, bits[5] = 2;
	val[6] = 2, bits[6] = 2;
	val[7] = 3, bits[7] = 2;

	long long ret = 0;
	int cur = 0;
  for (int i = 0; i < N; i += 3) {
  	int x = 4 * A[i] + 2 * A[i + 1] + A[i + 2];
  	if (!x) continue;

  	if (cur > 61) break;
  	ret += 1LL * val[x] * (1LL << cur);
  	cur += bits[x];
  }
  return ret;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2800 KB Output is correct - L* = 40
2 Correct 40 ms 3352 KB Output is correct - L* = 40
3 Correct 60 ms 3448 KB Output is correct - L* = 40
4 Correct 41 ms 3480 KB Output is correct - L* = 40
5 Correct 40 ms 3808 KB Output is correct - L* = 40
6 Correct 43 ms 3808 KB Output is correct - L* = 40
7 Correct 40 ms 3808 KB Output is correct - L* = 40
8 Correct 41 ms 3808 KB Output is correct - L* = 40
9 Correct 41 ms 3808 KB Output is correct - L* = 40
10 Correct 43 ms 3808 KB Output is correct - L* = 40
11 Correct 40 ms 3808 KB Output is correct - L* = 40
12 Correct 39 ms 3808 KB Output is correct - L* = 40
13 Correct 40 ms 3808 KB Output is correct - L* = 40
14 Correct 39 ms 3808 KB Output is correct - L* = 40
15 Correct 39 ms 3808 KB Output is correct - L* = 40
16 Correct 40 ms 3808 KB Output is correct - L* = 40
17 Correct 46 ms 3808 KB Output is correct - L* = 40
18 Correct 41 ms 3808 KB Output is correct - L* = 40
19 Correct 43 ms 3808 KB Output is correct - L* = 40
20 Correct 41 ms 3808 KB Output is correct - L* = 40
21 Correct 40 ms 3808 KB Output is correct - L* = 40
22 Correct 40 ms 3808 KB Output is correct - L* = 40
23 Correct 44 ms 3808 KB Output is correct - L* = 40
24 Correct 41 ms 3808 KB Output is correct - L* = 40
25 Correct 40 ms 3808 KB Output is correct - L* = 40
26 Correct 43 ms 3808 KB Output is correct - L* = 40
27 Correct 41 ms 3808 KB Output is correct - L* = 40
28 Correct 41 ms 3808 KB Output is correct - L* = 40
29 Correct 43 ms 3808 KB Output is correct - L* = 40
30 Correct 40 ms 3808 KB Output is correct - L* = 40
31 Correct 41 ms 3808 KB Output is correct - L* = 40
32 Correct 44 ms 3808 KB Output is correct - L* = 40
33 Correct 49 ms 3808 KB Output is correct - L* = 40
34 Correct 39 ms 3808 KB Output is correct - L* = 40
35 Correct 43 ms 3808 KB Output is correct - L* = 40
36 Correct 40 ms 3808 KB Output is correct - L* = 40
37 Correct 40 ms 3808 KB Output is correct - L* = 40
38 Correct 45 ms 3808 KB Output is correct - L* = 40
39 Correct 43 ms 3808 KB Output is correct - L* = 40
40 Correct 44 ms 3808 KB Output is correct - L* = 40