Submission #1349731

#TimeUsernameProblemLanguageResultExecution timeMemory
1349731julia_08Light Bulbs (EGOI24_lightbulbs)C++20
0 / 100
0 ms352 KiB
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 101;

int marc[MAXN][MAXN], dir[MAXN][MAXN];

int n;

pair<int, int> cell;

int ask(vector<pair<int, int>> v){

  cout << "?" << endl;

  vector<vector<int>> mat(n, vector<int> (n, 0));

  for(auto [x, y] : v) mat[x][y] = 1;

  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cout << mat[i][j];
    }
    cout << endl;
  }

  int ans; cin >> ans;
  return ans;

}

void answer(vector<pair<int, int>> v){

  cout << "!" << endl;

  vector<vector<int>> mat(n, vector<int> (n, 0));

  for(auto [x, y] : v) mat[x][y] = 1;

  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cout << mat[i][j];
    }
    cout << endl;
  }

}

int get(int x, int y){

  if(dir[x][y] != -1) return dir[x][y];

  int d = dir[cell.first][cell.second];
  return dir[x][y] = (ask({cell, {x, y}}) == 2 * n - 1 ? 1 - d : d);

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;

  vector<pair<int, int>> alive;

  vector<pair<int, int>> row, col;

  for(int i=0; i<n; i++) for(int j=0; j<n; j++) dir[i][j] = -1;

  int x = ask({{0, 0}, {1, 0}});

  if(x % n == 0){

    cell = {0, 0};

    marc[0][0] = marc[1][0] = 1;
    dir[0][0] = dir[1][0] = (x == 2 * n ? 0 : 1);

    if(dir[0][0] == 0){
      row = {{0, 0}, {1, 0}};
    } else col = {{0, 0}, {1, 0}};

  } else{

    // x = 2n - 1

    cell = {2, 0};

    marc[2][0] = 1;
    dir[2][0] = 0;

    if(ask({{0, 0}, {1, 0}, {2, 0}}) == 2 * n - 1) dir[2][0] = 1;

    if(dir[2][0] == 0){
      row = {{2, 0}};
    } else col = {{2, 0}};

  }

  for(auto [x, y] : row) for(int i=0; i<n; i++) marc[x][i] = 1;

  for(auto [x, y] : col) for(int i=0; i<n; i++) marc[i][y] = 1;

  for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(!marc[i][j]) alive.push_back({i, j});

  while(max((int) row.size(), (int) col.size()) < n){

    int i = rng() % (int) alive.size();

    marc[alive[i].first][alive[i].second] = 1;

    int cur = get(alive[i].first, alive[i].second);

    if(!cur) row.push_back(alive[i]);
    else col.push_back(alive[i]);

    for(int j=0; j<n; j++){
      if(!cur) marc[alive[i].first][j] = 1;
      else marc[j][alive[i].second] = 1;
    }

    vector<pair<int, int>> nalive;

    for(auto [x, y] : alive) if(!marc[x][y]) nalive.push_back({x, y});

    alive = nalive;

  }

  if((int) col.size() > (int) row.size()) swap(row, col);
  answer(row);

  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...