Submission #1062332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062332		PurpleCrayon	Light Bulbs (EGOI24_lightbulbs)	C++17	80 / 100	4 ms	836 KiB

Main

#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 / 11
• Subtask 2: 11 / 11
• Subtask 3: 58 / 78