QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#807466#9188. Light Bulbsucup-team0040 27ms3900kbC++237.0kb2024-12-10 00:31:262024-12-10 00:31:27

Judging History

你现在查看的是最新测评结果

  • [2024-12-10 00:31:27]
  • 评测
  • 测评结果：0
  • 用时：27ms
  • 内存：3900kb
查看
  • [2024-12-10 00:31:26]
  • 提交

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;
}
源文件, 语言: C++23

详细

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%
English 繁體中文 简体中文

服务器时间: 2024-12-12 12:38:41 | 开源项目