QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#555071#8558. Grid GamePhantomThresholdTL 0ms3580kbC++201.8kb2024-09-09 19:32:102024-09-09 19:32:10

Judging History

你现在查看的是最新测评结果

  • [2024-09-09 19:32:10]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3580kb
  • [2024-09-09 19:32:10]
  • 提交

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...

output:


result: