Submission #1329185

#TimeUsernameProblemLanguageResultExecution timeMemory
1329185avighnaLight Bulbs (EGOI24_lightbulbs)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

int main() {
  int n;
  cin >> n;

  auto is_same_as = [&](int i1, int j1, int i2, int j2) {
    cout << "?" << endl;
    vector<string> out(n, string(n, '0'));
    out[i1][j1] = out[i2][j2] = '1';
    for (auto &i : out) {
      cout << i << endl;
    }
    int x;
    cin >> x;
    return x % n == 0;
  };

  vector<string> grid(n, string(n, 'V'));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i == 0 && j == 0) {
        continue;
      }
      if (!is_same_as(0, 0, i, j)) {
        grid[i][j] = 'H';
      }
    }
  }

  vector dp(n + 1, vector<int>(n + 1, inf));
  for (int i = n; i >= 0; --i) {
    for (int j = n; j >= 0; --j) {
      if (i == n || j == n) {
        dp[i][j] = 0;
        continue;
      }
      for (int jj = j; jj < n; ++jj) { // choose horizontal to our right
        if (grid[i][jj] == 'H') {
          dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1);
        }
      }
      for (int ii = i; ii < n; ++ii) {
        if (grid[ii][j] == 'V') {
          dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1);
        }
      }
    }
  }

  vector<string> out(n, string(n, '0'));
  int i = 0, j = 0;
  while (i < n && j < n) {
    bool found = false;
    for (int jj = j; jj < n && !found; ++jj) {
      if (grid[i][jj] == 'H' && dp[i][j] == dp[i + 1][j] + 1) {
        out[i][jj] = '1';
        i++, found = true;
      }
    }
    for (int ii = i; ii < n && !found; ++ii) {
      if (grid[ii][j] == 'V' && dp[i][j] == dp[i][j + 1] + 1) {
        out[ii][j] = '1';
        j++, found = true;
      }
    }
  }

  cout << "!" << endl;
  for (auto &i : out) {
    cout << i << endl;
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...