QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#793356#9551. The EmperorTLE_AutomatWA 23ms12200kbC++232.8kb2024-11-29 18:57:192024-11-29 18:57:26

Judging History

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

  • [2024-11-29 18:57:26]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:12200kb
  • [2024-11-29 18:57:19]
  • 提交

answer

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

#define SZ(x) ((int)((x).size()))
#define lb(x) ((x) & (-(x)))
#define bp(x) __builtin_popcount(x)
#define bpll(x) __builtin_popcountll(x)
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
typedef __gnu_pbds::tree<pii, null_type, less<pii>, __gnu_pbds::rb_tree_tag, 
        __gnu_pbds::tree_order_statistics_node_update> rbt;

const int N = 1024;
const int Mod = 998244353;

void solve() {
    int n;
    scanf("%d", &n);
    vector opt(n + 1, 0);
    vector popx(n + 1, pii()), pushx(n + 1, pii());
    for (int i = 1; i <= n; i++) {
        char ch;
        scanf("\n%c", &ch);
        if (ch == 'P') {
            opt[i] = 0;
            scanf("OP %d GOTO %d; PUSH %d GOTO %d", &popx[i].fi, &popx[i].se, &pushx[i].fi, &pushx[i].se);
        } else {
            opt[i] = 1;
            scanf("ALT; PUSH %d GOTO %d", &pushx[i].fi, &pushx[i].se);
        }
    }

    vector f(N + 1, vector(N + 1, pii()));
    /* 第 p 条语句 , 当前栈顶是 x 
    *  x = 0 代表栈空
    *  p = 0 代表程序停机
    */
    int cnt = 0, lim = 3e6;
    auto dfs = [&](auto &&self, int p, int x) -> pii {
        if (f[p][x] != (pii){0, 0}) {
            return f[p][x];
        }
        cnt++;
        if (cnt > lim) {
            cout << -1 << '\n';
            exit(0);
        }

        if (opt[p] == 0 && x == popx[p].fi) {
            return f[p][x] = {1, popx[p].se};
        }
        else if (opt[p] == 1 && x == 0) {
            return f[p][x] = {1, 0};
        }
        else {
            auto curp = p;
            int step = 1;
            while (true) {
                cnt++;
                if (cnt > lim) {
                    cout << -1 << '\n';
                    exit(0);
                }
                
                // cout << "p = " << p << ", " << "x = " << x << '\n';
                // cout << "curp = " << curp << ", " << "x = " << x << '\n' << '\n';
                if (opt[curp] == 0 && popx[curp].fi == x) {
                    return f[p][x] = {(step + 1) % Mod, popx[curp].se};
                }
                if (opt[curp] == 1 && x == 0) {
                    return f[p][x] = {(step + 1) % Mod, 0};
                }
                auto res = self(self, pushx[curp].se, pushx[curp].fi);
                step = (step + res.fi) % Mod;
                curp = res.se;
            }
        }
    };
    auto ans = dfs(dfs, 1, 0);
    cout << ans.fi << '\n';
}

int main() {
    int T = 1;
    while (T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 11568kb

input:

1
HALT; PUSH 1 GOTO 1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 3ms
memory: 11360kb

input:

5
POP 1 GOTO 2; PUSH 1 GOTO 2
HALT; PUSH 1 GOTO 3
POP 1 GOTO 4; PUSH 2 GOTO 4
POP 1 GOTO 2; PUSH 2 GOTO 4
HALT; PUSH 99 GOTO 4

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 23ms
memory: 12200kb

input:

1
POP 1 GOTO 1; PUSH 1 GOTO 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: -100
Wrong Answer
time: 3ms
memory: 11484kb

input:

61
POP 62 GOTO 61; PUSH 30 GOTO 60
POP 1 GOTO 3; PUSH 62 GOTO 61
POP 2 GOTO 61; PUSH 62 GOTO 61
POP 4 GOTO 7; PUSH 2 GOTO 61
POP 62 GOTO 61; PUSH 3 GOTO 4
POP 62 GOTO 61; PUSH 3 GOTO 5
POP 5 GOTO 10; PUSH 3 GOTO 6
POP 62 GOTO 61; PUSH 4 GOTO 7
POP 62 GOTO 61; PUSH 4 GOTO 8
POP 6 GOTO 12; PUSH 4 GOTO...

output:

847249407

result:

wrong answer 1st numbers differ - expected: '150994941', found: '847249407'