QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#555071 | #8558. Grid Game | PhantomThreshold | TL | 0ms | 3580kb | C++20 | 1.8kb | 2024-09-09 19:32:10 | 2024-09-09 19:32:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
map<pair<vector<pair<int,int>>,int>,int> dict;
int dfs(vector<pair<int,int>> a,int tp){
if (a.size()==0){
if (tp==0) return 1;
else return 0;
}
{
bool flag=0;
for (auto [x,y]:a) if (x==0 && y==0) flag=1;
if (flag){
if (tp==0) return 0;
else return 1;
}
}
auto PAIR=make_pair(a,tp);
if (dict.count(PAIR)) return dict[PAIR];
int ans=0;
if (tp==0){
{
vector<pair<int,int>> nxt;
for (auto [x,y]:a){
if (x>0) nxt.emplace_back(x-1,y);
}
if (dfs(nxt,tp^1)==0) ans=1;
}
{
vector<pair<int,int>> nxt;
for (auto [x,y]:a){
if (y>0) nxt.emplace_back(x,y-1);
}
if (dfs(nxt,tp^1)==0) ans=1;
}
}
else{
int sz=(int)a.size();
for (int mask=0;mask<(1<<sz);mask++){
vector<pair<int,int>> nxt;
for (int i=0;i<sz;i++){
auto [x,y]=a[i];
if ((mask>>i)&1){
if (x>0) nxt.emplace_back(x-1,y);
}
else{
if (y>0) nxt.emplace_back(x,y-1);
}
}
if (dfs(nxt,tp^1)==0) ans=1;
}
}
return dict[PAIR]=ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int TC=1;
cin >> TC;
for (;TC--;){
int n;
cin >> n;
vector<pair<int,int>> a(n);
for (int i=0;i<n;i++){
cin >> a[i].first >> a[i].second;
}
int ans=dfs(a,0);
if (ans==1) cout << "Yes" << "\n";
else cout << "No" << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
3 1 3 3 2 2 0 1 2 4 2 0 2 3 1 6 5 2
output:
No Yes Yes
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: -100
Time Limit Exceeded
input:
1000 1 3 1 5 2 1 1 4 3 1 2 1 5 4 8 0 2 0 1 0 2 0 2 2 1 2 1 0 2 1 0 4 4 3 6 3 0 1 6 1 1 2 7 8 3 1 3 1 5 0 5 4 0 5 1 0 4 5 4 5 3 2 2 0 2 2 0 2 5 4 1 0 8 2 6 1 3 6 2 4 7 8 7 0 5 7 3 2 3 3 1 0 1 0 1 1 6 1 1 0 1 1 0 0 1 1 0 0 1 4 3 0 2 5 4 2 6 3 9 3 4 1 5 0 1 0 6 3 6 2 0 3 5 1 5 1 3 4 6 0 4 2 6 2 3 0 9 1...