QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783762#9551. The EmperorwlhWA 11ms3932kbC++174.0kb2024-11-26 11:42:442024-11-26 11:42:45

Judging History

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

  • [2024-11-26 11:42:45]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:3932kb
  • [2024-11-26 11:42:44]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 1024 + 10, inf = 1e9, mod = 998244353;

struct nb{
    int f, a, x, b, y;
}vt[N];

stack<int>st;
struct node{
    int cnt, v, b;
}dp[N][N];

int sum = 0;


void dfs(int u, int t) {
    sum ++;
    if(sum >= 1024 * 1024 + 10) {
        while(st.size()){
            st.pop();
        }
        return ;
    }
    if(dp[u][t].v) return ;
    if(vt[u].f == 1){
        int a = vt[u].a;
        if(st.size() && st.top() == vt[u].a){
            st.pop();
            // cout << "333 " << ' ' << u << ' ' << a << ' ' << vt[u].x << ' ' << (int)st.size() << ' ' << (int)st.top() << endl;
            dp[u][a] = {1, vt[u].x, st.top()};
            return ;
        }
        else{
            int b = vt[u].b;
            int tp = st.top(), sz = st.size();
            st.push(b);
            // cout << "b : " << b << ' ' << tp << endl;
            int y = vt[u].y, v = y;
            dp[u][tp].cnt = 1;
            dp[u][tp].b = tp;
            while((int)st.size() >= sz){
                dfs(v, t + 1);
                // cout << "111 " << u << ' ' << v << ' ' << b << ' ' << tp << ' ' << sz << ' ' << (int)st.size() << ' ' << dp[u][tp].cnt << endl;

                int cnt = dp[v][b].cnt;
                int vv = v, bb = b;
                v = dp[vv][bb].v;
                b = dp[vv][bb].b;

                dp[u][tp].cnt = (dp[u][tp].cnt + cnt) % mod;

                dp[u][tp].v = v;
                dp[u][tp].b = b;

                // cout << "222 " << u << ' ' << v << ' ' << b << ' ' << tp << ' ' << sz << ' ' << (int)st.size() << ' ' << dp[u][tp].cnt << endl;
                // cout << endl;

            }
            return ;
        }
    }
    else{
        if((int)st.size() == 1){
            st.pop();
            dp[u][0] = {1, 0, 0};
            return ;
        }
        else{
            int b = vt[u].b;
            int tp = st.top(), sz = st.size();
            st.push(b);
            // cout << "b : " << b << ' ' << tp << endl;
            int y = vt[u].y, v = y;
            dp[u][tp].cnt = 1;
            dp[u][tp].b = tp;
            while((int)st.size() >= sz){
                dfs(v, t + 1);
                // cout << "111 " << u << ' ' << v << ' ' << b << ' ' << tp << ' ' << sz << ' ' << (int)st.size() << ' ' << dp[u][tp].cnt << endl;

                int cnt = dp[v][b].cnt;
                int vv = v, bb = b;
                v = dp[vv][bb].v;
                b = dp[vv][bb].b;

                dp[u][tp].cnt = (dp[u][tp].cnt + cnt) % mod;
                dp[u][tp].v = v;
                dp[u][tp].b = b;

                // cout << "222 " << u << ' ' << v << ' ' << b << ' ' << tp << ' ' << sz << ' ' << (int)st.size() << ' ' << dp[u][tp].cnt << endl;
                // cout << endl;

            }
            return ;
        }
    }
}

void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        char c;
        cin >> c;
        if(c == 'P'){
            vt[i].f = 1;
            scanf("OP %d GOTO %d; PUSH %d GOTO %d", &vt[i].a, &vt[i].x, &vt[i].b, &vt[i].y);
        }
        else{
            vt[i].f = 2;
            scanf("ALT; PUSH %d GOTO %d", &vt[i].b, &vt[i].y);
        }
        // cout << vt[i].f << ' ' << vt[i].a << ' ' << vt[i].x << ' ' << vt[i].b << ' ' << vt[i].y << endl;
    }
    st.push(0);
    dfs(1, 0);

    // cout << dp[1][0].cnt << ' ' << dp[1][0].v << ' ' << dp[1][0].b << endl;
    // cout << dp[2][1].cnt << ' ' << dp[2][1].v << ' ' << dp[2][1].b << endl;
    // cout << dp[3][1].cnt << ' ' << dp[3][1].v << ' ' << dp[3][1].b << endl;

    if(sum == 1024 * 1024 + 10){
        cout << -1 << endl;
    }
    else{
        cout << dp[1][0].cnt << endl;
    }
    // cout << sum << endl;
}

signed main() {
    // std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
HALT; PUSH 1 GOTO 1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3752kb

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: 7ms
memory: 3928kb

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: 11ms
memory: 3928kb

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:

-1

result:

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