Submission #317317

#TimeUsernameProblemLanguageResultExecution timeMemory
317317AlexLuchianovBitwise (BOI06_bitwise)C++14
80 / 100
1 ms384 KiB
#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 = 29; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...