oj.uz

Submission #297033

# Submission time Handle Problem Language Result Execution time Memory
297033 2020-09-11T08:06:18 Z BThero Broken Device (JOI17_broken_device) C++17
100 / 100
 52 ms 3840 KB 
// chrono::system_clock::now().time_since_epoch().count()
#include "Annalib.h"
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

namespace {
  string V[] = {"", "0", "1", "00", "10", "11", "0", "01"};
  int n, k, bad_pos[45];
  int is_bad[205], mem[205];
  ll msg;  
  
  int bit(ll x, int p) {
    if (p > 60) return 0;
    return (x >> p) & 1;
  }
  
  void set(int p, int x) {
    if (p < n) {
      mem[p] = x;
    }
  }
  
  void send() {
    for (int i = 0; i < n; ++i) {
      Set(i, mem[i]);
    }
  }
  
  void solve() {
    fill(is_bad, is_bad + n, 0);
  
    for (int i = 0; i < k; ++i) {
      is_bad[bad_pos[i]] = 1;
    }
    
    fill(mem, mem + n, 0);
    int p = 0;
    
    for (int i = 0; i < n; i += 3) {
      string me;
      me.pb('0' + bit(msg, p));
      me.pb('0' + bit(msg, p + 1));
      int mask = 0;
      
      for (int j = 0; j < 3; ++j) {
        if (!is_bad[i + j]) {
          mask += (1 << j);
        }
      }
      
      if (__builtin_popcount(mask) < 2) {
        set(i, 0);
        set(i + 1, 0);
        set(i + 2, 0);
        continue;
      }
      
      int found1 = -1, found2 = -1;
      
      for (int s = 1; s < 8; ++s) {
        if ((mask & s) == s) {
          if (V[s].size() == 2 && V[s] == me) {
            found2 = s;
          }
          
          if (V[s].size() == 1 && V[s][0] == me[0]) {
            found1 = s;
          }
        }
      }
      
      assert(found1 != -1 || found2 != -1);
      
      if (found2 != -1) {
        set(i, bit(found2, 0));
        set(i + 1, bit(found2, 1));
        set(i + 2, bit(found2, 2));
        p += 2;
      }
      else {
        set(i, bit(found1, 0));
        set(i + 1, bit(found1, 1));
        set(i + 2, bit(found1, 2));
        p++;
      }
    }
    
    send();
  }
};

void Anna( int N, long long X, int K, int P[] ){
  n = N;
  msg = X;
  k = K;
  
  for (int i = 0; i < k; ++i) {
    bad_pos[i] = P[i];
  }

  solve();
}

// chrono::system_clock::now().time_since_epoch().count()
#include "Brunolib.h"
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

namespace {
  string V[] = {"", "0", "1", "00", "10", "11", "0", "01"};
  int n, arr[205];
  
  ll solve() {
    ll ret = 0;    
    int p = 0;
    
    for (int i = 0; i < n; i += 3) {
      int mask = arr[i] + arr[i + 1] * 2 + arr[i + 2] * 4;
      
      for (char c : V[mask]) {
        if (c == '1') {
          ret += (1ll << p);
        }
        
        ++p;
      }
    }
    
    return ret;
  }
};

long long Bruno( int N, int A[] ){
  n = N;
  
  for (int i = 0; i < n; ++i) {
    arr[i] = A[i];
  }

  return solve();
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3328 KB Output is correct - L* = 40
2 Correct 44 ms 3312 KB Output is correct - L* = 40
3 Correct 43 ms 3328 KB Output is correct - L* = 40
4 Correct 52 ms 3312 KB Output is correct - L* = 40
5 Correct 43 ms 3328 KB Output is correct - L* = 40
6 Correct 45 ms 3328 KB Output is correct - L* = 40
7 Correct 44 ms 3312 KB Output is correct - L* = 40
8 Correct 50 ms 3328 KB Output is correct - L* = 40
9 Correct 48 ms 3328 KB Output is correct - L* = 40
10 Correct 43 ms 3328 KB Output is correct - L* = 40
11 Correct 48 ms 3328 KB Output is correct - L* = 40
12 Correct 43 ms 3584 KB Output is correct - L* = 40
13 Correct 44 ms 3328 KB Output is correct - L* = 40
14 Correct 43 ms 3328 KB Output is correct - L* = 40
15 Correct 45 ms 3328 KB Output is correct - L* = 40
16 Correct 43 ms 3312 KB Output is correct - L* = 40
17 Correct 45 ms 3328 KB Output is correct - L* = 40
18 Correct 44 ms 3328 KB Output is correct - L* = 40
19 Correct 44 ms 3840 KB Output is correct - L* = 40
20 Correct 44 ms 3312 KB Output is correct - L* = 40
21 Correct 48 ms 3312 KB Output is correct - L* = 40
22 Correct 44 ms 3296 KB Output is correct - L* = 40
23 Correct 44 ms 3312 KB Output is correct - L* = 40
24 Correct 45 ms 3328 KB Output is correct - L* = 40
25 Correct 49 ms 3568 KB Output is correct - L* = 40
26 Correct 44 ms 3328 KB Output is correct - L* = 40
27 Correct 44 ms 3328 KB Output is correct - L* = 40
28 Correct 44 ms 3328 KB Output is correct - L* = 40
29 Correct 46 ms 3328 KB Output is correct - L* = 40
30 Correct 44 ms 3328 KB Output is correct - L* = 40
31 Correct 52 ms 3328 KB Output is correct - L* = 40
32 Correct 44 ms 3328 KB Output is correct - L* = 40
33 Correct 44 ms 3328 KB Output is correct - L* = 40
34 Correct 43 ms 3328 KB Output is correct - L* = 40
35 Correct 43 ms 3320 KB Output is correct - L* = 40
36 Correct 45 ms 3328 KB Output is correct - L* = 40
37 Correct 45 ms 3328 KB Output is correct - L* = 40
38 Correct 43 ms 3328 KB Output is correct - L* = 40
39 Correct 43 ms 3312 KB Output is correct - L* = 40
40 Correct 44 ms 3328 KB Output is correct - L* = 40