QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#793356 | #9551. The Emperor | TLE_Automat | WA | 23ms | 12200kb | C++23 | 2.8kb | 2024-11-29 18:57:19 | 2024-11-29 18:57:26 |
Judging History
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;
}
詳細信息
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'