oj.uz

Submission #926140

# Submission time Handle Problem Language Result Execution time Memory
926140 2024-02-12T15:33:53 Z parlimoos Bitwise (BOI06_bitwise) C++14
100 / 100
 1 ms 600 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , m;
vector<int> a;
vector<ui> b[100];
multiset<ui> ord[100];
ui sgs[100][2] , infs[100][2];

void init(){
    for(int i = 0 ; i < n ; i++){
        ui d = 0;
        for(int bit = 31 ; bit >= 0 ; bit--){
            if(((sgs[i][1] >> bit) & 1) != ((sgs[i][0] >> bit) & 1)) break;
            if(((sgs[i][1] >> bit) & 1)) d += (1 << bit);
        }
        infs[i][0] = d , infs[i][1] = (sgs[i][1] ^ d);
    }
    int l = 0;
    for(int i = 0 ; i < m ; i++){
        for(int j = l ; j < l + a[i] ; j++) b[i].pb(infs[j][0]) , ord[i].insert(infs[j][1]);
        l += a[i];
    }
}
bool jg(int inx , ui x){
    multiset<ui> q = ord[inx];
    for(ui el : b[inx]) x &= (~el);
    for(int bit = 31 ; bit >= 0 ;){
        int mx = *(--q.end());
        // cout << bit << " " << mx << "!!\n";
        if(((x >> bit) & 1) and !((mx >> bit) & 1)){
            // cout << bit << " " << mx << "::\n";
            return false;
        }
        if(!((x >> bit) & 1) and ((mx >> bit) & 1)) return true;
        if(((x >> bit) & 1) and ((mx >> bit) & 1)){
            q.erase(q.find(mx)) , q.insert(mx ^ (1 << bit));
            x ^= (1 << bit);
        }
        mx = *(--q.end());
        if(!((mx >> bit) & 1)) bit--;
    }
    if(x > 0) return false;
    return true;
}

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

    cin >> n >> m;
    for(int i = 0 ; i < m ; i++){
        int d;
        cin >> d;
        a.pb(d);
    }
    for(int i = 0 ; i < n ; i++) cin >> sgs[i][0] >> sgs[i][1];
    init();
    ui o = 0;
    // cout << jg(1 , 6) << "||\n";
    for(int bit = 31 ; bit >= 0 ; bit--){
        bool flg = 1;
        for(int i = 0 ; i < m ; i++) if(!jg(i , o ^ (1 << bit))) flg = 0;
        if(flg) o ^= (1 << bit);
    }
    cout << o;
}

Subtask #1
100.0 / 100.0

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