#include<bits/stdc++.h>
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
using namespace __gnu_pbds;
using namespace std;
using namespace __gnu_cxx;
using namespace std;
typedef long long ll;
vector < map < vector < int > , int > > state;
int rek(vector < int > S , int k){
if(state[k].find(S)!=state[k].end()){
return state[k][S];
}
ll s=0;
for(auto &i : S)s+=i;
if(s==0){
state[k][S] = 1;
return 1;
}
bool win = 0;
for(int i = 0; i < sz(S); ++i){
for(int x = 1; x <= min(k , S[i]); ++x){
S[i] -= x;
if(!rek(S,x)){
win = 1;
break;
}
S[i] += x;
}
}
state[k][S] = win;
return win;
}
int stupid(vector < int > S, int k){
if(k == 1){
long long xr = 0;
for(auto &i : S)
xr += i;
if(xr % 2 == 1)
return 1;
return 0;
}
state.clear();
state.resize(k + 1);
return rek(S , k);
}
signed slv(vector < int > S , int k)
{
using ll = long long ;
ll N = 0;
for(auto &i : S)
N += i;
ll cur = 1;
bool good = 0;
set < int > gd;
for(int i = 0 ; i< sz(S); ++i)
gd.insert(i);
while(cur <= k){
N = 0;
for(int i = 0; i < sz(S); ++i)
N += S[i];
if(N % 2 == 1){
good = 1;
break;
}
vector < int > del;
for(auto i : gd){
S[i] = (S[i] >> 1);
if(S[i] == 0){
del.pb(i);
}
}
for(auto u : del)
gd.erase(u);
cur <<= 1;
}
return good;
assert(false);
}
signed main(){
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--){
int n , k;
cin >> n >> k;
vector < int > S(n);
for(auto &i : S)
cin >> i;
cout << slv(S , k);
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
1400 KB |
Output is correct |
2 |
Correct |
24 ms |
1400 KB |
Output is correct |
3 |
Correct |
22 ms |
1356 KB |
Output is correct |
4 |
Correct |
22 ms |
1408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
316 KB |
Output is correct |
2 |
Correct |
14 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
380 KB |
Output is correct |
2 |
Correct |
28 ms |
340 KB |
Output is correct |
3 |
Correct |
27 ms |
336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
43 ms |
380 KB |
Output is correct |
2 |
Correct |
44 ms |
328 KB |
Output is correct |
3 |
Correct |
40 ms |
352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
1356 KB |
Output is correct |
2 |
Correct |
23 ms |
1356 KB |
Output is correct |
3 |
Correct |
26 ms |
1404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
1404 KB |
Output is correct |
2 |
Correct |
25 ms |
2288 KB |
Output is correct |
3 |
Correct |
37 ms |
2360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
1380 KB |
Output is correct |
2 |
Correct |
38 ms |
2396 KB |
Output is correct |