oj.uz

Submission #260340

# Submission time Handle Problem Language Result Execution time Memory
260340 2020-08-10T06:10:48 Z Namnamseo Broken Device (JOI17_broken_device) C++17
100 / 100
 78 ms 3584 KB 
#include <bits/stdc++.h>
#include "Annalib.h"
using namespace std;

static bool gen;

static bitset<150> key_orig[60];
static bitset<150> key[60];

static void GEN(){
    if(gen) return;
    srand(12345);
    for(int i=0; i<60; ++i){
        for(int j=0; j<150; ++j){
            key_orig[i][j] = rand()%2;
        }
    }
    gen=1;
}

void Anna(int N, long long X, int K, int P[]){
    GEN();
    
    int bit[60];
    for(int i=0; i<60; ++i) bit[i] = (1&(X >> i));
    
    for(int i=0; i<60; ++i){
        key[i]=key_orig[i];
        for(int j=0; j<K; ++j) key[i][P[j]]=0;
    }
    int row_ind = 0;
    int key_row[60];
    for(int j=0; j<150 && row_ind<60; ++j){
        bool has_key = 1;
        if(!key[row_ind][j]){
            has_key = 0;
            for(int i=row_ind+1; i<60; ++i) if(key[i][j]){
                {
                    auto tmp=key[row_ind];
                    key[row_ind]=key[i];
                    key[i]=tmp;
                }
                swap(bit[row_ind], bit[i]);
                has_key=1; break;
            }
        }
        if(!has_key) continue;
        for(int i=row_ind+1; i<60; ++i) if(key[i][j]){
            bit[i] ^= bit[row_ind];
            key[i] ^= key[row_ind];
        }
        key_row[row_ind]=j;
        ++row_ind;
    }
    if(row_ind != 60){
        for(int i=0; i<150; ++i) Set(i, 0);
        return;
    }
    bitset<150> ans;
    for(int i=59; 0<=i; --i) if(bit[i]){
        int col = key_row[i];
        for(int j=0; j<60; ++j){
            bit[j] ^= key[j][col];
        }
        ans[col]=1;
    }
    for(int i=0; i<150; ++i) Set(i, ans[i]);
}

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

static bool gen;

static bitset<60> key[150];

static void GEN(){
    if(gen) return;
    srand(12345);
    for(int i=0; i<60; ++i){
        for(int j=0; j<150; ++j){
            key[j][i] = rand()%2;
        }
    }
    gen=1;
}

long long Bruno( int N, int A[] ){
    GEN();
    bitset<60> ret;
    for(int i=0; i<150; ++i) if(A[i]){
        ret ^= key[i];
    }
    auto ans=0ll;
    for(int i=0; i<60; ++i){
        if(ret[i]) ans += (1ll << i);
    }
    return ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 3312 KB Output is correct - L* = 40
2 Correct 61 ms 3312 KB Output is correct - L* = 40
3 Correct 65 ms 3312 KB Output is correct - L* = 40
4 Correct 62 ms 3208 KB Output is correct - L* = 40
5 Correct 58 ms 3312 KB Output is correct - L* = 40
6 Correct 60 ms 3312 KB Output is correct - L* = 40
7 Correct 65 ms 3312 KB Output is correct - L* = 40
8 Correct 60 ms 3312 KB Output is correct - L* = 40
9 Correct 59 ms 3312 KB Output is correct - L* = 40
10 Correct 64 ms 3312 KB Output is correct - L* = 40
11 Correct 64 ms 3320 KB Output is correct - L* = 40
12 Correct 63 ms 3312 KB Output is correct - L* = 40
13 Correct 61 ms 3312 KB Output is correct - L* = 40
14 Correct 60 ms 3312 KB Output is correct - L* = 40
15 Correct 68 ms 3312 KB Output is correct - L* = 40
16 Correct 60 ms 3312 KB Output is correct - L* = 40
17 Correct 60 ms 3312 KB Output is correct - L* = 40
18 Correct 60 ms 3312 KB Output is correct - L* = 40
19 Correct 59 ms 3312 KB Output is correct - L* = 40
20 Correct 61 ms 3312 KB Output is correct - L* = 40
21 Correct 60 ms 3312 KB Output is correct - L* = 40
22 Correct 59 ms 3312 KB Output is correct - L* = 40
23 Correct 60 ms 3312 KB Output is correct - L* = 40
24 Correct 60 ms 3312 KB Output is correct - L* = 40
25 Correct 69 ms 3576 KB Output is correct - L* = 40
26 Correct 64 ms 3568 KB Output is correct - L* = 40
27 Correct 59 ms 3312 KB Output is correct - L* = 40
28 Correct 60 ms 3568 KB Output is correct - L* = 40
29 Correct 60 ms 3312 KB Output is correct - L* = 40
30 Correct 61 ms 3312 KB Output is correct - L* = 40
31 Correct 59 ms 3312 KB Output is correct - L* = 40
32 Correct 60 ms 3568 KB Output is correct - L* = 40
33 Correct 67 ms 3312 KB Output is correct - L* = 40
34 Correct 67 ms 3584 KB Output is correct - L* = 40
35 Correct 62 ms 3312 KB Output is correct - L* = 40
36 Correct 60 ms 3312 KB Output is correct - L* = 40
37 Correct 64 ms 3312 KB Output is correct - L* = 40
38 Correct 65 ms 3312 KB Output is correct - L* = 40
39 Correct 61 ms 3312 KB Output is correct - L* = 40
40 Correct 78 ms 3312 KB Output is correct - L* = 40