QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#246387#7104. Halting Problemucup-team2190#ML 1ms3512kbC++202.5kb2023-11-10 19:40:342023-11-10 19:40:35

Judging History

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

  • [2023-11-10 19:40:35]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:3512kb
  • [2023-11-10 19:40:34]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;

#define int long long
#define endl "\n"

#ifdef LOCAL_SYS
#include "debug.h"
#else
#define dbg(...)
#endif


void solve(){
    int n;
    cin >> n;
    map<string, int> mp;
    mp["add"] = 1, mp["beq"] = 2, mp["bne"] = 3, mp["blt"] = 4, mp["bgt"] = 5;
    vector<vector<int>> v(n, vector<int> (3));
    for(int i = 0;i < n;i++){
        string s;
        cin >> s;
        v[i][0] = mp[s];
        if(v[i][0] == 1){
            cin >> v[i][1];
        }
        else{
            cin >> v[i][1] >> v[i][2];
            v[i][2]--;
        }
    }
    
    const int MOD = 256;
    vector<vector<int>> dp(n+5, vector<int> (260, 0));
    function <int(int,int)> f = [&](int ind, int val){
        if(ind == n) return 0ll;
        if(dp[ind][val] == 1) return 1ll; // loop
        
        dp[ind][val] = 1;
        if(v[ind][0] == 1){
            return f(ind+1, (val + v[ind][1])%MOD);
        }
        else{
            int cur = v[ind][0], idx = v[ind][2], c = v[ind][1];
            if(cur == 2 && c == val){
                return f(idx, val);
            }
            else if(cur == 2){
                return f(ind+1, val);
            }
            
            if(cur == 3 && c != val){
                return f(idx, val);
            }
            else if(cur == 3){
                return f(ind+1, val);
            }
            
            if(cur == 4 && c > val){
                return f(idx, val);
            }
            else if(cur == 4){
                return f(ind+1, val);
            }
            
            if(cur == 5 && c < val){
                return f(idx, val);
            }
            else if(cur == 5){
                return f(ind+1, val);
            }
        }
        
        return 0ll;
    };
    
    int x = f(0, 0);
    cout << ( x ? "No" : "Yes") << endl;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #ifdef LOCAL_SYS
        freopen("error.txt", "w", stderr);
        auto start = chrono::high_resolution_clock::now();
        cerr << fixed << setprecision(4);
    #endif
      
    int t = 1;
    cin >> t;
    for(int i = 1;i <= t;i++){
      solve();
    }

    #ifdef LOCAL_SYS
        auto stop = chrono::high_resolution_clock::now();
        auto duration = chrono::duration_cast<chrono::nanoseconds> (stop - start);
        cerr << endl << "Time: " << ((long double)duration.count())/((long double)1e9) << "s " << endl;
    #endif

  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3512kb

input:

4
2
add 1
blt 5 1
3
add 252
add 1
bgt 252 2
2
add 2
bne 7 1
3
add 1
bne 252 1
beq 252 1

output:

Yes
Yes
No
No

result:

ok 4 lines

Test #2:

score: -100
Memory Limit Exceeded

input:

1117
8
bgt 51 8
add 75
add 115
bne 40 3
beq 213 6
bgt 210 4
blt 228 7
bgt 60 2
6
bne 130 3
add 33
bne 74 4
blt 73 6
blt 63 5
bne 138 2
6
beq 131 2
bgt 90 3
add 127
bgt 195 1
blt 244 6
bne 20 3
3
add 53
bne 122 1
blt 251 2
9
add 102
add 161
bne 26 2
blt 5 8
beq 76 3
add 119
bgt 196 3
bne 239 8
blt 15...

output:


result: