Submission #1168040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168040		KaleemRazaSyed	Walk (POI13_spa)	C++20	25 / 100	5101 ms	273348 KiB

spa

#include<bits/stdc++.h>

using namespace std;

#define int long long

int read()
{
  string s;
  cin >> s;
  int res = 0;
  for(char c : s)
    res <<= 1, res += c - '0';
  return res;
}

signed main()
{
  int n, k;
  cin >> n >> k;
  int x = read(), y = read();
  int a[k];
  for(int i = 0; i < k; i ++)
    a[i] = read();

  sort(a, a + k);

  queue<int> Q1, Q2;
  bool poss = (x == y);

  set<int> seen1, seen2;
  
  Q1.push(x);
  Q2.push(y);

  while(Q1.size() && Q2.size() && !poss)
    {
      int u = Q1.front();
      Q1.pop();
      for(int i = 0; i < n; i ++)
	{
	  int v = u ^ (1LL << i);
	  if(binary_search(a, a + k, v)) continue;
	  if(seen2.count(v))
	    poss = true;
	  else if(!seen1.count(v))
	    seen1.insert(v), Q1.push(v);
	}

      u = Q2.front();
      Q2.pop();
      for(int i = 0; i < n; i ++)
	{	
	  int v = u ^ (1LL << i);
	  if(binary_search(a, a + k, v)) continue;
	  if(seen1.count(v))
	    poss = true;
	  else if(!seen2.count(v))
	    seen2.insert(v), Q2.push(v);
	}
    }
  
  cout << (poss ? "TAK" : "NIE") << endl;
  return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 13 / 13
• Subtask 8: 0 / 13