Submission #1220715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220715		SpyrosAliv	Light Bulbs (EGOI24_lightbulbs)	C++20	0 / 100	0 ms	420 KiB

Main

#include <bits/stdc++.h>
using namespace std;

// n / height + max(n * log(height), n / height * logn) queries (hopefully)

int H = 4;
int n;

int query(vector<vector<bool>> &grid) {
    cout << "? " << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << grid[i][j];
        }
        cout << endl;
    }
    int tot; cin >> tot;
    return tot;
}

void ans(vector<vector<bool>> &grid) {
    cout << "! " << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << grid[i][j];
        }
        cout << endl;
    }
}

int find_col(int st) {
    int lo = 1, hi = n;
    int fin = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        vector<vector<bool>> willAsk(n+1, vector<bool>(n+1, false));
        for (int i = st; i <= min(n, st + H - 1); i++) {
            for (int j = 1; j <= mid; j++) {
                willAsk[i][j] = true;
            }
        }
        int tot = query(willAsk);
        if (tot >= (mid-1) * n + (n - (mid - 1)) * min(H, n - st + 1)) {
            fin = mid;
            hi = mid-1;
        }
        else lo = mid+1;
    }
    return fin;
}

void get_good(int h) {
    vector<vector<bool>> finGrid(n+1, vector<bool>(n+1, false));
    for (int j = 1; j <= n; j++) {
        int lo = h, hi = min(n, h + H - 1);
        int finIdx = -1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            vector<vector<bool>> willAsk(n+1, vector<bool>(n+1, false));
            for (int i = h; i <= mid; i++) {
                willAsk[i][j] = true;
            }
            int tot = query(willAsk);
            int E = (mid - h) * n + n - (mid - 1) + h - 1;
            if (tot >= E) {
                finIdx = mid;
                hi = mid-1;
            }
            else lo = mid+1;
        }
        finGrid[finIdx][j] = 1;
    }
    ans(finGrid);
}

void solve() {
    cin >> n;
    H = min(H, n - 1);
    for (int h = 1; h <= n; h += H) {
        vector<vector<bool>> willAsk(n+1, vector<bool>(n+1, false));
        for (int i = h; i <= min(h + H - 1, n); i++) {
            for (int j = 1; j <= n; j++) {
                willAsk[i][j] = true;
            }
        }
        int tot = query(willAsk);
        if (tot == n*n) {
            get_good(h);
            return;
        }
        else continue;
    }
    vector<vector<bool>> finGrid(n+1, vector<bool>(n+1, false));
    for (int h = 1; h <= n; h += H) {
        int col = find_col(h);
        for (int i = h; i <= min(n, h + H - 1); i++) {
            finGrid[i][col] = true;
        }
    }
    ans(finGrid);
}

int main() {
    int t = 1;
    while (t--) solve();
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 78