제출 #1329192

#제출 시각아이디문제언어결과실행 시간메모리
1329192avighnaLight Bulbs (EGOI24_lightbulbs)C++20
22 / 100
64 ms448 KiB
#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

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

  auto query = [&](const vector<string> &out) {
    cout << "?" << endl;
    for (auto &i : out) {
      cout << i << endl;
    }
    int x;
    cin >> x;
    return x;
  };

  auto is_same_as = [&](int i1, int j1, int i2, int j2) {
    vector<string> out(n, string(n, '0'));
    out[i1][j1] = out[i2][j2] = '1';
    return query(out) % n == 0;
  };

  auto run_bs = [&](char c) {
    vector<string> grid(n, string(n, c));
    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] = c == 'V' ? 'H' : 'V';
        }
      }
    }

    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;
        }
      }
    }

    return out;
  };

  string s = "VH";
  random_device rd;
  if (rd() & 1) {
    swap(s[0], s[1]);
  }
  for (char &i : s) {
    auto out = run_bs(i);
    if (query(out) == n * n) {
      cout << "!" << endl;
      for (auto &i : out) {
        cout << i << endl;
      }
      return 0;
    }
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...