Submission #1252762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252762		badge881	Light Bulbs (EGOI24_lightbulbs)	C++20	54.25 / 100	391 ms	496 KiB

Main

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

int n;
set<int> row, col;

int ask(vector<pair<int, int>> &v)
{
    vector<vector<int>> A(n, vector<int>(n, 0));
    for (pair<int, int> p : v)
    {
        int a = p.first;
        int b = p.second;
        A[a][b] = 1;
    }
    cout << "?" << endl;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << A[i][j];
        }
        cout << endl;
    }
    int x;
    cin >> x;
    return x;
}

void answer(vector<pair<int, int>> &v)
{
    vector<vector<int>> A(n, vector<int>(n, 0));
    for (pair<int, int> p : v)
    {
        int a = p.first;
        int b = p.second;
        A[a][b] = 1;
    }
    cout << "! " << endl;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << A[i][j];
        }
        cout << endl;
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        row.insert(i);
        col.insert(i);
    }
    vector<pair<int, int>> q;
    q.push_back({0, 0});
    q.push_back({1, 0});
    int x = ask(q);
    int bef = x;
    pair<int, int> bosoo = {0, 0}, hevtee = {0, 0};
    set<int> hev[n], bos[n];
    bool ok = 0;
    if (x == n * 2)
    {
        hev[0].insert(0);
        hev[1].insert(0);
        row.erase(0);
        row.erase(1);
        ok = 1;
    }
    else if (x == n)
    {
        bos[0].insert(0);
        bos[0].insert(1);
        col.erase(0);
        ok = 1;
    }
    bool is_hev = 1;
    for (int i = 2; i < n; i++)
    {
        q.push_back({i, 0});
        int x = ask(q);
        if (x < bef + n - 1)
        {
            bos[0].insert(i);
            is_hev = 0;
            bef = x;
        }
        else
        {
            bef = x;
            hev[i].insert(0);
            row.erase(i);
            is_hev = 1;
        }
    }
    if (!ok)
    {
        q.clear();
        q.push_back({n - 1, 0});
        q.push_back({0, 0});
        x = ask(q);
        if (is_hev)
        {
            if (x == n * 2)
            {
                hev[0].insert(0);
                bos[0].insert(1);
                row.erase(0);
                col.erase(0);
            }
            else
            {
                bos[0].insert(0);
                hev[1].insert(0);
                row.erase(1);
                col.erase(0);
            }
        }
        else
        {
            if (x == n)
            {
                bos[0].insert(0);
                hev[1].insert(0);
                row.erase(1);
                col.erase(0);
            }
            else
            {
                hev[0].insert(0);
                bos[0].insert(1);
                row.erase(0);
                col.erase(0);
            }
        }
    }
    if (row.size() == 0)
    {
        q.clear();
        for (int i = 0; i < n; i++)
        {
            if (!hev[i].empty())
                q.push_back({i, *hev[i].begin()});
        }
        answer(q);
        return 0;
    }
    ok = 1;
    for (int X : row)
    {
        pair<int, int> bosoo = {-1, -1};
        for (int Y : bos[0])
            bosoo = {Y, 0};
        q.clear();
        q.push_back(bosoo);
        for (int i = 1; i < n; i++)
        {
            q.push_back({X, i});
        }
        int x = ask(q);
        if (x == n * n)
        {
            ok = 0;
            break;
        }
        int l = 1, r = n - 1;
        while (l < r)
        {
            int mid = (l + r) / 2;
            q.clear();
            q.push_back(bosoo);
            for (int i = l; i <= mid; i++)
            {
                q.push_back({X, i});
            }
            int x = ask(q);
            if (x < (mid - l + 2) * n)
                r = mid;
            else
                l = mid + 1;
        }
        hev[X].insert(l);
    }
    q.clear();
    if (ok)
    {
        for (int i = 0; i < n; i++)
        {
            if (!hev[i].empty())
                q.push_back({i, *hev[i].begin()});
        }
        answer(q);
        return 0;
    }
    q.clear();
    q.push_back({0, 0});
    q.push_back({0, 1});
    x = ask(q);
    bef = x;
    if (x == n * 2)
    {
        bos[0].insert(0);
        bos[1].insert(0);
        col.erase(0);
        col.erase(1);
        ok = 1;
    }
    else if (x == n)
    {
        hev[0].insert(0);
        hev[0].insert(1);
        row.erase(0);
        ok = 1;
    }
    is_hev = 1;
    for (int i = 2; i < n; i++)
    {
        q.push_back({0, i});
        int x = ask(q);
        if (x < bef + n - 1)
        {
            hev[0].insert(i);
            is_hev = 1;
            bef = x;
        }
        else
        {
            bef = x;
            bos[i].insert(0);
            col.erase(i);
            is_hev = 0;
        }
    }
    if (!ok)
    {
        q.clear();
        q.push_back({0, n - 1});
        q.push_back({0, 0});
        x = ask(q);
        if (!is_hev)
        {
            if (x == n * 2)
            {
                bos[0].insert(0);
                hev[0].insert(1);
                row.erase(0);
                col.erase(0);
            }
            else
            {
                bos[1].insert(0);
                hev[0].insert(1);
                row.erase(0);
                col.erase(1);
            }
        }
        else
        {
            if (x == n)
            {
                bos[1].insert(0);
                hev[0].insert(0);
                row.erase(0);
                col.erase(1);
            }
            else
            {
                hev[0].insert(1);
                bos[0].insert(0);
                row.erase(0);
                col.erase(0);
            }
        }
    }
    ok = 1;
    for (int X : col)
    {
        for (int Y : hev[0])
        {
            hevtee = {0, Y};
        }
        q.clear();
        q.push_back(hevtee);
        for (int i = 1; i < n; i++)
        {
            q.push_back({i, X});
        }
        int x = ask(q);
        if (x == n * n)
        {
            ok = 0;
            break;
        }
        int l = 1, r = n - 1;
        while (l < r)
        {
            int mid = (l + r) / 2;
            q.clear();
            q.push_back(hevtee);
            for (int i = l; i <= mid; i++)
            {
                q.push_back({i, X});
            }
            int x = ask(q);
            if (x < (mid - l + 2) * n)
                r = mid;
            else
                l = mid + 1;
        }
        bos[X].insert(l);
    }
    q.clear();
    if (ok)
    {
        for (int i = 0; i < n; i++)
        {
            if (!bos[i].empty())
                q.push_back({*bos[i].begin(), i});
        }
        answer(q);
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~

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