# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
977829 | nguyentunglam | Broken Device (JOI17_broken_device) | C++17 | 195 ms | 3004 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "Annalib.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
mt19937 rng(145);
const int m = 110, T = 60;
bitset<m + 1> a[T];
long long rnd(long long l, long long r) {
return l + rng() % (r - l + 1);
}
}
void Anna( int n, long long x, int k, int P[] ){
vector<long long> b(m);
for(int i = 0; i < T; i++) {
for(int j = 0; j < m; j++) a[i][j] = rnd(0, 1);
a[i][m] = x >> i & 1;
}
vector<bool> broken(n, 0);
for(int i = 0; i < k; i++) broken[P[i]] = 1;
for(int i = 0; i < m; i++) if (broken[i]) {
for(int j = 0; j < T; j++) a[j][i] = 0;
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < T; j++) if (a[j][i]) b[i] |= (1 << j);
}
// for(int i = 0; i < m; i++) cout << b[i] << endl;
vector<int> pos(T, -1);
for(int col = 0, row = 0; col < m && row < T; col++) {
for(int i = row; i < T; i++) if (a[i][col]) {
swap(a[i], a[row]);
break;
}
if (a[row][col] == 0) continue;
pos[row] = col;
for(int i = 0; i < T; i++) if (i != row && a[i][col]) a[i] ^= a[row];
row++;
}
// for(int i = 0; i < T; i++) cout << a[i] << endl;
vector<int> ans(m, 0);
for(int i = 0; i < T; i++) {
int x = pos[i];
ans[x] = a[i][m];
}
int Xor = 0;
for(int i = 0; i < m; i++) if (ans[i]) Xor ^= b[i];
// cout << Xor << endl;
for(int i = 0; i < m; i++) Set(i, ans[i]);
for(int i = m; i < n; i++) Set(i, 0);
}
#include "Brunolib.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
mt19937 rng(145);
const int m = 110, T = 60;
bitset<m + 1> a[60];
long long rnd(long long l, long long r) {
return l + rng() % (r - l + 1);
}
}
long long Bruno( int N, int A[] ){
// vector<long long> b(m);
for(int i = 0; i < T; i++) {
for(int j = 0; j < m; j++) a[i][j] = rnd(0, 1);
}
//
// for(int i = 0; i < m; i++) {
// for(int j = 0; j < T; j++) if (a[j][i]) b[i] |= (1 << j);
// }
long long ans = 0;
for(int i = 0; i < T; i++) {
int sum = 0;
for(int j = 0; j < m; j++) if (A[j]) sum ^= a[i][j];
if (sum) ans |= (1LL << i);
}
// cout << ans << endl;
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |