QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#807466 | #9188. Light Bulbs | ucup-team004 | 0 | 27ms | 3900kb | C++23 | 7.0kb | 2024-12-10 00:31:26 | 2024-12-10 00:31:27 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
constexpr bool debug = false;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N;
std::cin >> N;
std::vector<std::string> lights(N);
if (debug) {
for (int i = 0; i < N; i++) {
std::cin >> lights[i];
}
}
std::vector<std::array<int, 3>> determined;
std::vector<std::array<int, 2>> candidates;
std::vector<int> possible {0};
int cnt[2] {};
std::vector lit(N, std::vector<bool>(N));
std::vector type(N, std::vector<int>(N, -1));
std::vector candId(N, std::vector<int>(N, -1));
auto calc = [&](const std::vector<std::array<int, 2>> &q, int s) -> int {
std::vector<bool> row(N), col(N);
for (auto [x, y] : q) {
if (type[x][y] != -1) {
if (type[x][y] == 0) {
row[x] = true;
} else {
col[y] = true;
}
} else {
if (s >> candId[x][y] & 1) {
col[y] = true;
} else {
row[x] = true;
}
}
}
return N * N - std::count(row.begin(), row.end(), false) * std::count(col.begin(), col.end(), false);
};
while (cnt[0] < N && cnt[1] < N) {
if (debug) {
std::cerr << "candidates : " << candidates.size() << ", possibilities : " << possible.size() << "\n";
for (auto [x, y] : candidates) {
std::cerr << "(" << x << ", " << y << ") ";
}
std::cerr << "\n";
for (auto s : possible) {
for (int i = 0; i < candidates.size(); i++) {
std::cerr << (s >> i & 1);
}
std::cerr << " ";
}
std::cerr << "\n";
}
while (possible.size() <= 512) {
std::array<int, 2> add {-1, -1};
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!lit[i][j] && candId[i][j] == -1) {
add = {i, j};
}
}
}
if (add[0] == -1) {
break;
}
for (int i = possible.size() - 1; i >= 0; i--) {
possible.push_back(possible[i] | 1 << candidates.size());
}
candId[add[0]][add[1]] = candidates.size();
candidates.push_back(add);
}
std::vector<std::array<int, 2>> query;
int E = 1E9;
for (int t = 0; t < 512; t++) {
std::vector<std::array<int, 2>> q;
for (auto [a, b, c] : determined) {
if (rng() % 2) {
q.push_back({a, b});
}
}
for (auto [a, b] : candidates) {
if (rng() % 2) {
q.push_back({a, b});
}
}
std::map<int, int> freq;
for (auto s : possible) {
freq[calc(q, s)]++;
}
int ent = 0;
for (auto [_, c] : freq) {
ent += c * c;
}
if (ent < E) {
E = ent;
query = q;
}
}
std::cout << "?\n";
std::vector choose(N, std::vector<bool>(N));
for (auto [a, b] : query) {
choose[a][b] = true;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
std::cout << choose[i][j];
}
std::cout << "\n";
}
std::cout.flush();
int result;
if (debug) {
std::vector<bool> row(N), col(N);
for (auto [x, y] : query) {
if (lights[x][y] == 'H') {
row[x] = true;
} else {
col[y] = true;
}
}
result = N * N - std::count(row.begin(), row.end(), false) * std::count(col.begin(), col.end(), false);
std::cerr << result << "\n";
} else {
std::cin >> result;
}
{
std::vector<int> newPossible;
for (auto s : possible) {
if (debug) {
std::cerr << s << " expected : " << calc(query, s) << "\n";
}
if (calc(query, s) == result) {
newPossible.push_back(s);
}
}
possible = std::move(newPossible);
}
int maybe[2] {};
for (auto s : possible) {
maybe[0] |= ((1 << candidates.size()) - 1) ^ s;
maybe[1] |= s;
}
std::vector<std::array<int, 2>> newCand;
for (int i = 0; i < candidates.size(); i++) {
auto [x, y] = candidates[i];
if ((maybe[0] ^ maybe[1]) >> i & 1) {
if (!lit[x][y]) {
int t = maybe[0] >> i & 1 ? 0 : 1;
cnt[t]++;
if (t == 0) {
for (int j = 0; j < N; j++) {
lit[x][j] = true;
}
} else {
for (int j = 0; j < N; j++) {
lit[j][y] = true;
}
}
determined.push_back({x, y, t});
}
candId[x][y] = -1;
} else {
candId[x][y] = newCand.size();
newCand.push_back({x, y});
}
}
for (auto &s : possible) {
int ns = 0;
for (int i = 0; i < candidates.size(); i++) {
if (s >> i & 1) {
auto [x, y] = candidates[i];
if (candId[x][y] != -1) {
ns |= 1 << candId[x][y];
}
}
}
s = ns;
}
std::sort(possible.begin(), possible.end());
possible.erase(std::unique(possible.begin(), possible.end()), possible.end());
candidates = std::move(newCand);
}
int t = cnt[0] == N ? 0 : 1;
std::cout << "!\n";
std::vector choose(N, std::vector<bool>(N));
for (auto [a, b, c] : determined) {
if (c == t) {
choose[a][b] = true;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
std::cout << choose[i][j];
}
std::cout << "\n";
}
std::cout.flush();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 11
Accepted
time: 17ms
memory: 3596kb
input:
3 9 9 9 3
output:
? 010 011 010 ? 001 101 001 ? 100 011 100 ? 000 110 000 ! 010 010 010
result:
points 1.0 points 1.0 correct, 4 queries
Test #2:
score: 11
Accepted
time: 20ms
memory: 3736kb
input:
3 9 9
output:
? 111 100 000 ? 000 010 111 ! 011 000 100
result:
points 1.0 points 1.0 correct, 2 queries
Test #3:
score: 11
Accepted
time: 19ms
memory: 3604kb
input:
3 5 9
output:
? 000 111 010 ? 001 011 001 ! 001 001 001
result:
points 1.0 points 1.0 correct, 2 queries
Test #4:
score: 11
Accepted
time: 17ms
memory: 3812kb
input:
3 9 5
output:
? 100 100 101 ? 001 001 011 ! 100 100 010
result:
points 1.0 points 1.0 correct, 2 queries
Test #5:
score: 11
Accepted
time: 27ms
memory: 3900kb
input:
3 7 8 7 7 8
output:
? 010 110 010 ? 001 111 000 ? 100 101 100 ? 100 000 111 ? 011 000 101 ! 001 001 010
result:
points 1.0 points 1.0 correct, 5 queries
Test #6:
score: 0
Time Limit Exceeded
input:
3 5 9 5 5 5 7 5 9 3 7 7 3 5 6 9 3 7 9 9 6 6 7 3 9 7 5 9 9 3 6 6 6 0 5 9 7 9 6 6 3 3 9 5 6 3 6 6 9 3 7 9 7 7 3 3 7 7 7 7 9 9 6 3 6 6 5 7 0 7 7 9 7 9 7 3 3 3 9 5 9 5 3 7 7 3 9 5 9 9 6 3 7 6 7 6 9 9 5 5 7 7 3 7 3 7 7 3 5 3 7 9 3 6 5 7 9 9 7 5 3 7 5 6 9 3 7 6 5 7 7 3 3 0 6 9 3 9 3 7 9 3 9 6 3 9 3 9 7 5 ...
output:
? 001 001 101 ? 010 111 010 ? 100 100 101 ? 010 010 100 ? 000 100 100 ? 000 110 100 ? 010 010 100 ? 010 101 000 ? 010 010 000 ? 010 011 100 ? 010 100 100 ? 010 000 000 ? 010 010 100 ? 000 101 000 ? 010 101 000 ? 000 010 000 ? 000 101 100 ? 000 111 000 ? 000 111 100 ? 000 101 000 ? 000 101 000 ? 010 ...
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%