이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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) + (S[i] & 1);
if(S[i] == 1){
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |