oj.uz

Submission #1062332

# Submission time Handle Problem Language Result Execution time Memory
1062332 2024-08-17T03:23:58 Z PurpleCrayon Light Bulbs (EGOI24_lightbulbs) C++17
80 / 100
 4 ms 836 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 50, MOD = 1e9+7;
const ll INF = 1e18+10;

void solve() {
    int n; cin >> n;
    vector<int> row_ord(n), col_ord(n);
    iota(row_ord.begin(), row_ord.end(), 0);
    iota(col_ord.begin(), col_ord.end(), 0);

    random_shuffle(row_ord.begin(), row_ord.end());
    random_shuffle(col_ord.begin(), col_ord.end());

    auto pr = [&](vector<pair<int, int>> v) {
        vector<string> g(n, string(n, '0'));
        for (auto [i, j] : v) g[i][j] = '1';
        for (auto& r : g) cout << r << '\n';
        cout.flush();
    };

    int si = row_ord[0], sj = col_ord[0];
    bool h_top = true;
    auto get_type = [&](int i, int j, bool b) { // b is true if I know the type of si sj already
        if (b) {
            cout << "?\n";
            pr({make_pair(i, j), make_pair(si, sj)});
            int cnt; cin >> cnt;
            return bool(h_top ^ (cnt % 2));
        }

        // query all of first row
        //      if n^2: return
        //      otherwise: there must be at least one H
        //                  count V (n + v * (n - 1))

        auto cnt_v = [&](int ci, int cj) {
            vector<pair<int, int>> v;
            for (int k = 0; k < n; k++) if (k != cj)
                v.emplace_back(ci, k);

            cout << "?\n";
            pr(v);
            int cnt; cin >> cnt;
            if (cnt == n * sz(v)) // all V
                return sz(v);

            int cur_v = (cnt - n) / (n - 1);
            assert(n + cur_v * (n - 1) == cnt);
            return cur_v;
        };

        return !bool(cnt_v(si, -1) - cnt_v(si, sj));
    };

    h_top = get_type(si, sj, false);
    int p1 = 0, p2 = 0;
    vector<pair<int, int>> hs, vs;
    if (h_top) p1++, hs.emplace_back(si, sj);
    else p2++, vs.emplace_back(si, sj);

    while (sz(hs) < n && sz(vs) < n) {
        if (get_type(row_ord[p1], col_ord[p2], true)) {
            hs.emplace_back(row_ord[p1++], col_ord[p2]);
        } else {
            vs.emplace_back(row_ord[p1], col_ord[p2++]);
        }
    }

    if (sz(hs) < sz(vs)) swap(vs, hs); // print hs
    cout << "!\n";
    pr(hs);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 0 ms 416 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 0 ms 344 KB Output is correct
38 Correct 1 ms 344 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 0 ms 344 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 0 ms 344 KB Output is correct
43 Correct 0 ms 344 KB Output is correct
44 Correct 0 ms 344 KB Output is correct
45 Correct 0 ms 344 KB Output is correct
46 Correct 0 ms 344 KB Output is correct
47 Correct 0 ms 344 KB Output is correct
48 Correct 0 ms 344 KB Output is correct
49 Correct 0 ms 344 KB Output is correct
50 Correct 0 ms 344 KB Output is correct
51 Correct 0 ms 344 KB Output is correct
52 Correct 0 ms 344 KB Output is correct
53 Correct 0 ms 344 KB Output is correct
54 Correct 1 ms 344 KB Output is correct
55 Correct 0 ms 344 KB Output is correct
56 Correct 1 ms 344 KB Output is correct
57 Correct 0 ms 344 KB Output is correct
58 Correct 0 ms 344 KB Output is correct
59 Correct 0 ms 344 KB Output is correct

Subtask #3
58.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 0 ms 344 KB Output is correct
38 Correct 0 ms 344 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 0 ms 344 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 0 ms 356 KB Output is correct
43 Correct 1 ms 356 KB Output is correct
44 Correct 1 ms 356 KB Output is correct
45 Correct 0 ms 356 KB Output is correct
46 Correct 0 ms 356 KB Output is correct
47 Correct 0 ms 356 KB Output is correct
48 Correct 1 ms 356 KB Output is correct
49 Correct 0 ms 356 KB Output is correct
50 Correct 0 ms 356 KB Output is correct
51 Correct 0 ms 356 KB Output is correct
52 Correct 0 ms 356 KB Output is correct
53 Correct 1 ms 356 KB Output is correct
54 Correct 0 ms 356 KB Output is correct
55 Correct 0 ms 356 KB Output is correct
56 Correct 1 ms 356 KB Output is correct
57 Correct 0 ms 356 KB Output is correct
58 Correct 0 ms 356 KB Output is correct
59 Partially correct 2 ms 492 KB Partially correct
60 Partially correct 1 ms 492 KB Partially correct
61 Partially correct 2 ms 836 KB Partially correct
62 Partially correct 2 ms 492 KB Partially correct
63 Partially correct 4 ms 492 KB Partially correct
64 Partially correct 3 ms 472 KB Partially correct
65 Partially correct 3 ms 480 KB Partially correct
66 Partially correct 4 ms 472 KB Partially correct
67 Partially correct 4 ms 480 KB Partially correct
68 Partially correct 3 ms 480 KB Partially correct
69 Partially correct 2 ms 480 KB Partially correct
70 Partially correct 3 ms 480 KB Partially correct
71 Partially correct 2 ms 472 KB Partially correct
72 Partially correct 3 ms 472 KB Partially correct
73 Partially correct 2 ms 480 KB Partially correct
74 Partially correct 2 ms 480 KB Partially correct
75 Partially correct 2 ms 472 KB Partially correct
76 Partially correct 2 ms 480 KB Partially correct
77 Partially correct 3 ms 480 KB Partially correct
78 Partially correct 3 ms 632 KB Partially correct
79 Partially correct 2 ms 480 KB Partially correct
80 Partially correct 3 ms 480 KB Partially correct
81 Partially correct 3 ms 480 KB Partially correct
82 Partially correct 3 ms 664 KB Partially correct
83 Partially correct 3 ms 480 KB Partially correct
84 Partially correct 3 ms 696 KB Partially correct
85 Partially correct 3 ms 480 KB Partially correct
86 Partially correct 2 ms 480 KB Partially correct
87 Partially correct 2 ms 728 KB Partially correct
88 Partially correct 2 ms 480 KB Partially correct
89 Partially correct 1 ms 712 KB Partially correct
90 Partially correct 2 ms 472 KB Partially correct
91 Partially correct 2 ms 696 KB Partially correct
92 Partially correct 3 ms 480 KB Partially correct
93 Partially correct 3 ms 480 KB Partially correct
94 Partially correct 4 ms 472 KB Partially correct
95 Partially correct 3 ms 480 KB Partially correct
96 Partially correct 3 ms 480 KB Partially correct
97 Correct 0 ms 344 KB Output is correct