제출 #1349716

#제출 시각아이디문제언어결과실행 시간메모리
1349716julia_08Light Bulbs (EGOI24_lightbulbs)C++20
61.73 / 100
183 ms572 KiB
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 101;

int n;

bool swp = false;

vector<int> p[MAXN];

vector<vector<int>> transpose(vector<vector<int>> &mat){

  vector<vector<int>> ret = mat;

  for(int i=0; i<mat.size(); i++){
    for(int j=0; j<mat[i].size(); j++){
      ret[j][i] = mat[i][j];
    }
  }

  return ret;

}

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

  cout << "?" << endl;

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

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

  if(swp) mat = transpose(mat);

  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[p[y][x]][y] = 1;

  if(swp) mat = transpose(mat);

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

}

vector<pair<int, int>> col(int j, int i){

  vector<pair<int, int>> ret;

  for(int k=0; k<=i; k++) ret.push_back({k, j});
  return ret;

}

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

  cin >> n;

  vector<pair<int, int>> ans;

  for(int i=0; i<n; i++){

    p[i].resize(n);
    for(int j=0; j<n; j++) p[i][j] = j;

    shuffle(p[i].begin(), p[i].end(), rng);
  
  }

  if(rng() % 2) swp = true;

  vector<int> rows;

  for(int i=0; i<n; i++) rows.push_back(i);

  shuffle(rows.begin(), rows.end(), rng);

  for(auto i : rows){

    int x = ask(col(i, 1));

    if(x != 2 * n){

      if(x == n){
        ans.push_back({0, i});
        continue;
      }

      // entao x = 2n - 1

      if(ask(col(i, 2)) == x){
        ans.push_back({2, i});
        continue;
      }

      if(ask({{0, i}, {2, i}}) != 2 * n){
        ans.push_back({0, i});
      } else ans.push_back({1, i});

      continue;

    }

    int l = 2, r = n;

    while(l < r){
      int m = l + (r - l) / 2;
      if(ask(col(i, m)) != (m + 1) * n) r = m;
      else l = m + 1;
    }

    if(r == n){
      answer(col(i, n - 1));
      return 0;
    }

    ans.push_back({r, i});

  }

  answer(ans);

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