Codeforces_CompCodes/CF1405C.cpp at main · masterishaan19/Codeforces_CompCodes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<bits/stdc++.h>
using namespace std;
#define ll int long long
#define mp make_pair
//#define for(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define N 1000000007
#define pq priority queue
#define pb push_back
#define pf push_front
#define mt make_tuple
#define prec(a) fixed<<setprecision(9)<<a
#define endl "\n"
#define fast_set s.max_load_factor(0.25);s.reserve(500);
#define cy cout<<"YES"<<endl;
#define cn cout<<"NO"<<endl;
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
const long double PI = (long double)(3.1415926535897932384626433832795);

int main()
{
	fast;
	int test,n,i,j,k;
	cin>>test;
	while(test--)
	{
		cin>>n>>k;
		string str;
		cin>>str;
		string ans=""; // default string with all question marks.
		for(i=0;i<k;i++)
		{
			ans+="?";
		}
		bool flag=true;
		int zero=0,one=0,que=0; // count of number of zeroes, ones and question marks in string.
		for(i=0;i<k;i++)
		{
			if(str[i]=='0')
			{
				zero++;
			}
			else if(str[i]=='1')
			{
				one++;
			}
			else
			{
				que++;
			}
		}

		int req=k/2;
		if(zero>req||one>req)
		{
			flag=false;
		}
		for(i=k;i<n;i++)
		{
			// including current char.
			if(str[i]=='0')
			{
				zero++;
			}
			else if(str[i]=='1')
			{
				one++;
			}
			else
			{
				que++;
			}

			// excluding last char.
			if(str[i-k]=='0')
			{
				zero--;
			}
			else if(str[i-k]=='1')
			{
				one--;
			}
			else
			{
				que--;
			}
			if(zero>req||one>req)
			{
				flag=false;
			}
		}
		for(i=0;i<n;i++)
		{
			if(str[i]!='?')
			{
				if(ans[i%k]=='?')
				{
					ans[i%k]=str[i];
				}
				else
				{
					if(ans[i%k]==str[i])
					{

					}
					else
					{
						flag=false;
					}
				}
			}
		}
		zero=0;
		one=0;
		for(i=0;i<k;i++)
		{
			if(ans[i]=='0')
			{
				zero++;
			}
			else if(ans[i]=='1')
			{
				one++;
			}
		}
		if(zero>req||one>req)
		{
			flag=false;
		}
		if(flag)
		{
			cy; // output YES
		}
		else
		{
			cn; // output NO.
		}
	}
	return 0;
}