QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #526939 | #6341. The Last Battle | Qwerty1232 | 0 | 0ms | 0kb | C++23 | 5.3kb | 2024-08-22 02:20:52 | 2024-08-22 02:20:54 |
Anna
#include "Anna.h"
#include <bits/stdc++.h>
namespace {
using u64 = uint64_t;
constexpr int n = 8;
std::vector<u64> gen() {
constexpr int K = 64;
std::mt19937_64 rnd(2086 + 1329);
std::vector<u64> vec(K);
std::vector<u64> res;
while (res.size() < K) {
u64 val0 = rnd();
if (__builtin_popcountll(val0) != 32) {
continue;
}
u64 val = val0;
for (int j = 0; j < K; j++) {
if (val & 1ULL << j) {
if (vec[j]) {
val ^= vec[j];
} else {
vec[j] = val;
res.push_back(val0);
break;
}
}
}
}
return res;
}
const std::vector<u64> data = gen();
} // namespace
void Anna(int X, int Y, int N, std::string s) {
u64 mask = 0;
for (int i = 0; i < N; i++) {
if (s[i] == 'B') {
mask ^= data[i];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != X && j != Y) {
Paint(i, j, mask >> i * n + j & 1);
}
}
}
}
Bruno
#pragma GCC optimize("O3")
#pragma GCC target("avx2,bmi,bmi2")
#include "Bruno.h"
#include <bits/stdc++.h>
namespace {
using u64 = uint64_t;
constexpr int n = 8;
std::vector<u64> gen() {
constexpr int K = 64;
std::mt19937_64 rnd(2086 + 1329);
std::vector<u64> vec(K);
std::vector<u64> res;
while (res.size() < K) {
u64 val0 = rnd();
if (__builtin_popcountll(val0) != 32) {
continue;
}
u64 val = val0;
for (int j = 0; j < K; j++) {
if (val & 1ULL << j) {
if (vec[j]) {
val ^= vec[j];
} else {
vec[j] = val;
res.push_back(val0);
break;
}
}
}
}
return res;
}
const std::vector<u64> data = gen();
} // namespace
std::string Bruno(int N, std::vector<std::vector<int>> T) {
// if (N >= 30) {
// return std::string(N, 'A');
// }
u64 mask = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mask |= u64(T[i][j]) << i * n + j;
}
}
std::vector<std::pair<int, u64>> ans;
std::vector<u64> data2(64);
std::vector<std::pair<int, int>> all_xy;
for (int i = 0; i < n * n; i++) {
all_xy.push_back({i / n, i % n});
}
static std::mt19937 rnd;
// std::shuffle(all_xy.begin(), all_xy.end(), rnd);
// for (int x = 0; x < n; x++) {
// for (int y = 0; y < n; y++) {
for (auto [x, y] : all_xy) {
u64 mk = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mk |= u64(i == x || j == y) << i * n + j;
}
}
for (int i = 0; i < n * n; i++) {
data2[i] = data[i] & ~mk;
}
std::vector<u64> vec(n * n);
for (int i = 0; i < n * n; i++) {
if (i / n == x || i % n == y) {
continue;
}
u64 val = 0;
for (int j = 0; j < N; j++) {
val |= (data2[j] >> i & 1) << j;
}
val |= u64(T[i / n][i % n]) << N;
vec[i] = val;
}
bool fucked = false;
std::vector<u64> fuck(N);
for (int i = 0; i < vec.size(); i++) {
u64 val = vec[i];
// for (int j = 0; j < N; j++) {
for (int j = 0; j < N; j = __builtin_ctzll(val)) {
if (val >> j & 1) {
if (fuck[j]) {
val ^= fuck[j];
} else {
fuck[j] = val;
val = 0;
break;
}
}
}
if (val) {
fucked = true;
break;
}
}
if (std::count(fuck.begin(), fuck.end(), 0)) {
fucked = true;
}
if (fucked) {
continue;
}
for (int i = N - 1; i >= 0; i--) {
for (int j = i + 1; j < N; j++) {
if (fuck[i] >> j & 1) {
fuck[i] ^= fuck[j];
}
}
}
u64 res = 0;
for (int i = 0; i < N; i++) {
res |= (fuck[i] >> N & 1) << i;
}
ans.push_back({x * n + y, res});
break;
}
// if (ans.size()) {
// break;
// }
// }
assert(ans.size() >= 1);
std::map<u64, int> map;
for (auto [xy, val] : ans) {
map[val]++;
}
std::pair<int, u64> max(0, 0);
for (auto [a, b] : map) {
max = std::max(max, {b, a});
}
u64 ans_mask = max.second;
std::string ans_str(N, '-');
for (int i = 0; i < N; i++) {
ans_str[i] = "AB"[ans_mask >> i & 1];
}
return ans_str;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Stage 1: Program Anna Time Limit Exceeded
Manager to Anna
20000 1 7 1 A 2 3 1 A 0 1 1 A 1 1 1 A 7 4 1 A 2 3 1 A 0 3 1 B 0 7 1 A 4 2 1 B 5 4 1 A 6 0 1 B 7 3 1 A 0 7 1 A 2 3 1 A 1 6 1 A 5 2 1 B 2 7 1 B 6 3 1 A 3 3 1 A 1 7 1 A 2 3 1 A 1 2 1 A 5 3 1 A 3 5 1 A 4 3 1 A 2 3 1 A 4 6 1 B 7 3 1 B 2 3 1 A 4 4 1 A 7 3 1 A 4 5 1 B 0 7 1 A 0 3 1 B 2 0 1 B 4 1 1 A 6 0 1 ...