#include <bits/stdc++.h>
#define m_p make_pair
#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<x)
#define sz(x) (int)x.size()
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<long long,long long> pll;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
auto rng=bind(uniform_int_distribution<int>(1,20),mt19937(time(0)));
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
map<pair<multiset<int>,int>,int>dp;
int k;
int rec(multiset<int> vc,int h){
if(dp.count({vc,h})) return dp[{vc,h}];
int ok=0;
for(auto &x : vc){
for(int j=min(h,x);j>=1;j--){
multiset<int> nw=vc;
nw.erase(nw.find(x));nw.insert(x-j);
if(!rec(nw,j)) ok=1;
}
if(ok) break;
}
dp[{vc,h}]=ok;
return ok;
}
signed main(){
fast_ioi;
int t;
// t=1;
cin>>t;
srand(228);
while(t--){
int n;
// n=3;k=2;
// n=rand()%10+1;k=rand()%5+1;
cin>>n>>k;
// vec<int>a;
vec<int>a(n);
// for(auto &z : a) z=rand()%3+1;
for(auto &z : a) cin>>z;
// debug()<<imie(a);
auto brute=[&](){
// dp.clear();
multiset<int>st;
for(auto &z : a) st.insert(z);
return rec(st,k);
};
auto solve=[&](){
vec<ll>cnt(32,0);
for(int i=0;i<31;i++){
if(pw(i)>k) break;
for(int j=0;j<n;j++){
cnt[i]+=(a[j]/pw(i));
}
}
// debug()<<imie(a);
for(int i=0;i<32;i++){
if(cnt[i]%2) return 1;
}
return 0;
};
// if(*max_element(all(a))<=3){
// cout<<brute();
// continue;
// }
// if(k!=1 && k!=2){
// cout<<brute();
// }
// else{
// cout<<solve();
// }
// if(brute()!=solve()){
// debug()<<imie(a)imie(solve())imie(brute())imie(k);
// return 0;
// }
cout<<solve();
// debug()<<imie(brute())imie(solve());
}
return 0;
}
/*
6 1
5447 7526 7703 8705 18716 19718 19895
1582 7087 7911 14379 14703 14703 19265 19265 19589 26057 32386
*/
Compilation message
football.cpp: In function 'int main()':
football.cpp:83:14: warning: variable 'brute' set but not used [-Wunused-but-set-variable]
83 | auto brute=[&](){
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
400 KB |
Output is correct |
| 2 |
Correct |
16 ms |
332 KB |
Output is correct |
| 3 |
Correct |
16 ms |
396 KB |
Output is correct |
| 4 |
Correct |
14 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
332 KB |
Output is correct |
| 2 |
Correct |
10 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
364 KB |
Output is correct |
| 2 |
Correct |
37 ms |
372 KB |
Output is correct |
| 3 |
Correct |
35 ms |
388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
1732 KB |
Output is correct |
| 2 |
Correct |
49 ms |
2028 KB |
Output is correct |
| 3 |
Correct |
62 ms |
2168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
332 KB |
Output is correct |
| 2 |
Correct |
16 ms |
400 KB |
Output is correct |
| 3 |
Correct |
18 ms |
396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
1224 KB |
Output is correct |
| 2 |
Correct |
19 ms |
1284 KB |
Output is correct |
| 3 |
Correct |
30 ms |
1352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1228 KB |
Output is correct |
| 2 |
Correct |
35 ms |
1360 KB |
Output is correct |
