Submission #1151726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151726		KaleemRazaSyed	Light Bulbs (EGOI24_lightbulbs)	C++20	0 / 100	0 ms	408 KiB

Main

#include<bits/stdc++.h>

using namespace std;

int n;
int ask(vector<pair<int,int> > vec)
{
  bool out[n][n];
  memset(out, false, sizeof(out));
  for(auto [x, y] : vec) out[x][y] = 1;

  cout << "?" << endl;
  for(int i = 0; i < n; i ++) {
    for(int j = 0; j < n; j++)
      cout << out[i][j];
    cout << endl;
  }
  int res;
  cin >> res;
  return res;
}

void say(vector<pair<int,int> > vec)
{
  bool out[n][n];
  memset(out, false, sizeof(out));
  for(auto [x, y] : vec) out[x][y] = 1;

  cout << "!" << endl;
  for(int i = 0; i < n; i ++) {
    for(int j = 0; j < n; j++)
      cout << out[i][j];
    cout << endl;
  }
  exit(0);
}

void solve(int idx, int res)
{
  for(int i = idx; i < n; i ++)
    {
      vector<pair<int,int> > on;
      for(int j = 0; j < n; j ++)
	on.push_back({i, j});
      if(ask(on) == n * n)
	say(on);
    }

  vector<pair<int,int> > sol;
  
  if(res == n)
    {
      sol.push_back({idx, 0});
      for(int i = 0; i < idx; i ++)
	{
	  if(ask({{i, 0}, {idx, 0}}) == 2 * n)
	    sol.push_back({i, 0});
	  else
	    sol.push_back({i, n - 1});
	}

      for(int i = idx + 1; i < n; i ++)
	{
	  int l = 0, r = n;
	  while(r - l > 1)
	    {
	      int mid = (l + r) / 2;
	      vector<pair<int,int> > on = {{idx, 0}};
	      for(int j = 0; j < mid; j ++)
		on.push_back({i, j});

	      if(ask(on) == n + mid * n - mid)
		l = mid;
	      else
		r = mid;
	    }
	  sol.push_back({i, l});
	}
      say(sol);
    }

  for(int i = 0; i < idx; i ++)
    {
      if(ask({{idx, 0}, {i, 0}}) == n)
	sol.push_back({i, n - 1});
      else
	sol.push_back({i, 0});
    }
  
  for(int i = idx; i < n; i ++)
    {
      int l = 0, r = n;
      while(r - l > 1)
	{
	  int mid = (l + r) / 2;
	  vector<pair<int,int> > on = {{idx, 0}};
	  for(int j = 0; j < mid; j++)
	    on.push_back({i, j});

	  if(ask(on) == mid * n)
	    l = mid;
	  else
	    r = mid;
	}
      sol.push_back({i, l});
    }
  say(sol);
}

int main()
{
  cin >> n;
  
  for(int i = 0; i < n; i ++)
    {
      int res = ask({{i, 0}, {i, n - 1}});
      if(res != 2 * n - 1)
	solve(i, res);
    }
  assert(false);
  vector<pair<int,int> > sol = {{0, 0}}, sol2 = {{0, n-1}};
  for(int i = 1; i < n; i ++) // if the first is <->
    {
      int res1 = ask({{0, 0}, {i, 0}});
      int res2 = ask({{0, n -1}, {i, 0}});

      if(res1 == 2 * n)
	sol.push_back({i, 0});
      else
	sol.push_back({i, n-1});

      if(res2 == 2 * n)
	sol2.push_back({i, 0});
      else
	sol2.push_back({i, n - 1});
    }

  if(ask(sol2) == n * n)
    say(sol2);
  say(sol);
  return 0;
}

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