oj.uz

Submission #317319

# Submission time Handle Problem Language Result Execution time Memory
317319 2020-10-29T12:39:40 Z AlexLuchianov Bitwise (BOI06_bitwise) C++14
100 / 100
 1 ms 512 KB 
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>


using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100;
int const lgmax = 30;

int v[1 + nmax][2], cap[1 + nmax][2];
int aux[1 + nmax][2];

bool solve(int start, int stop, int target) {
  for(int i = start; i <= stop ;i++) {
    aux[i][0] = v[i][0];
    aux[i][1] = v[i][1];
  }

  for(int bit = lgmax; 0 <= bit; bit--) {
    if(0 == ((1 << bit) & target)) {
      for(int i = start; i <= stop; i++)
        if((aux[i][0] & (1 << bit)) < (aux[i][1] & (1 << bit)))
          return true;
    } else {
      int _count1 = 0, _count01 = 0;
      for(int i = start; i <= stop; i++) 
        if((aux[i][0] & (1 << bit)) == (1 << bit))
          _count1++;
        else if((aux[i][0] & (1 << bit)) < (aux[i][1] & (1 << bit)))
          _count01++;
      if(1 < _count01)
        return true;
      else if(0 < _count1 && 0 < _count01)
        return true;
      else if(0 == _count1 && 0 == _count01)
        return false;
      else 
        for(int i = start; i <= stop; i++)
          if((aux[i][0] & (1 << bit)) < (aux[i][1] & (1 << bit)))
            aux[i][0] = 0;
    }
  }
  return true;
}

bool general_solve(int k, int target) {
  bool verdict = true;
  for(int i = 1;i <= k; i++)
    verdict &= solve(cap[i][0], cap[i][1], target);
  return verdict;
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n, k;
  std::cin >> n >> k;
  int last = 0;
  for(int i = 1;i <= k; i++) {
    int val;
    std::cin >> val;
    cap[i][0] = last + 1;
    last += val;
    cap[i][1] = last;
  }

  for(int i = 1;i <= n; i++)
    std::cin >> v[i][0] >> v[i][1];
  int result = 0;
  
  for(int jump = (1 << lgmax); 0 < jump; jump /= 2) {
    if(general_solve(k, result + jump) == 1)
      result += jump;
  }
  std::cout << result;
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 512 KB Output is correct