Submission #1248223

#TimeUsernameProblemLanguageResultExecution timeMemory
1248223badge881Light Bulbs (EGOI24_lightbulbs)C++20
0 / 100
0 ms408 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;

int ask(const vector<pair<int, int>> &cells)
{
    vector<vector<int>> A(n, vector<int>(n, 0));
    for (auto [x, y] : cells)
        A[x][y] = 1;
    cout << "?\n";
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << A[i][j];
        cout << '\n';
    }
    cout.flush();
    int res;
    cin >> res;
    return res;
}

void answer(const vector<pair<int, int>> &cells)
{
    vector<vector<int>> A(n, vector<int>(n, 0));
    for (auto [x, y] : cells)
        A[x][y] = 1;
    cout << "!\n";
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << A[i][j];
        cout << '\n';
    }
    cout.flush();
}

vector<pair<int, int>> find_positions()
{
    vector<pair<int, int>> result;
    vector<bool> used_col(n, false);
    for (int row = 0; row < n; row++)
    {
        int low = 0, high = n - 1, col = -1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            vector<pair<int, int>> test = result;
            for (int j = 0; j <= mid; j++)
            {
                if (!used_col[j])
                {
                    test.emplace_back(row, j);
                    break;
                }
            }
            int res = ask(test);
            if (res == (int)test.size() * n)
            {
                col = mid;
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        while (used_col[col])
            col++;
        used_col[col] = true;
        result.emplace_back(row, col);
    }
    return result;
}

int main()
{
    cin >> n;
    vector<pair<int, int>> res = find_positions();
    answer(res);
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...