1405C - Balanced Bitstring - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cout.tie(NULL);
#define int long long
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
const int INF = 0x3f3f3f3f;

void debug(set<int> s) {
  for (int i : s) {
    cout << i << " ";
  }
  cout << endl;
}

void debug(unordered_set<int> s) {
  for (int i : s) {
    cout << i << " ";
  }
  cout << endl;
}

void debug(vector<string> s) {
  for (string i : s) {
    cout << i << " ";
  }
  cout << endl;
}

void debug(vector<pii> v) { 
  cout << "PAIR START" << endl;
  for (auto i : v) {
    cout << i.first << " " << i.second << endl;
  }
  cout << "PAIR END" << endl;
}

void debug(vector<int> v) { 
  for (int i : v) {
    cout << i << " ";
  }
  cout << endl;
}

void debug(map<int, int> v) { 
  cout << "PAIR START" << endl;
  for (auto i : v) {
    cout << i.first << " " << i.second << endl;
  }
  cout << "PAIR END" << endl;
}

void debug(vector<vector<int>> adj) {
  for (vector<int> i : adj) {
    for (int j : i) {
      cout << j << " ";
    }
    cout << endl;
  }
}
 
void iohelp(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

ll max(ll a, ll b) {
  return a > b ? a : b;
}

ll min(ll a, ll b) {
  return a < b ? a : b;
}

void sol() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  int d = k / 2;
  
  vector<char> corr(k, '?');
  for (int i = 0; i < n; ++i) {
    char c = s[i];

    if (c == '1') {
      if (corr[i % k] == '0') {
        cout << "NO" << endl;
        return;
      }
      corr[i % k] = '1';
    }
    else if (c == '0') {
      if (corr[i % k] == '1') {
        cout << "NO" << endl;
        return;
      }
      corr[i % k] = '0';
    }
  }

  for (int i = 0; i < n; ++i) {
    if (s[i] == '?') {
      s[i] = corr[i % k];
    }
  }

  int oc = 0, zc = 0;
  for (int i = 0; i < k; ++i) {
    if (s[i] == '1') {
      oc++;
    }
    else if (s[i] == '0') {
      zc++;
    }
  }
  if (max(oc, zc) > d) {
    cout << "NO" << endl; return;
  }
  cout << "YES" << endl;
}
 
int32_t main() {
  fastio;
  int t;
  cin >> t;
  for (int i = 1; i <= t; ++i) {
    sol();
  }
}