QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #771574 | #9551. The Emperor | Nana7 | WA | 5ms | 20300kb | C++14 | 1.8kb | 2024-11-22 14:19:19 | 2024-11-22 14:19:22 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#define I inline
#define mkp make_pair
#define int long long
#define pii pair<long long,long long>
using namespace std;
const int mod = 998244353;
const int N = 1030;
struct Node {
int type;
int a,b,x,y;
}ins[N];
struct node {
int cnt,v;
node(int _c=0,int _v=0) {
cnt=_c; v=_v;
}
};
node f[N][N];
int n,flag;
string s;
map< pii ,int> mp;
I bool digit(char x) {
return x<='9'&&x>='0';
}
vector<int> getnum() {
vector<int> ret;
int len=s.length(),num=0;
//cout<<len<<endl;
for(int i=0;i<len;++i) {
if(!digit(s[i])) {
if(num) ret.push_back(num);
// cout<<num<<endl;
num=0;
} else {
num=num*10+s[i]-'0';
}
}
if(num) ret.push_back(num);
return ret;
}
node dp(int id,int tp) {
if(flag) return node(0,0);
if(mp[mkp(id,tp)]==1) {
flag=1; return node(0,0);
}
mp[mkp(id,tp)]=1;
if(f[id][tp].cnt!=-1) return f[id][tp];
if(ins[id].type==1&&tp==ins[id].a) {
f[id][tp]=node(1,ins[id].x);
} else if(ins[id].type==2&&tp==0){
f[id][tp]=node(1,0);
} else {
node mk=dp(ins[id].y,ins[id].b);
if(mk.v==0) {
f[id][tp]=node(1+mk.cnt,0);
} else {
node mk2=dp(mk.v,tp);
f[id][tp]=node(mk2.cnt+mk.cnt+1,mk2.v);
}
}
f[id][tp].cnt%=mod;
mp[mkp(id,tp)]=0;
return f[id][tp];
}
signed main()
{
cin>>n; char ch=getchar();
for(int i=1;i<=n;++i) {
getline(cin,s);
vector<int> v=getnum();
if(v.size()==2) {
ins[i].type=2;
ins[i].b=v[0];
ins[i].y=v[1];
} else {
ins[i].type=1;
ins[i].a=v[0];
ins[i].x=v[1];
ins[i].b=v[2];
ins[i].y=v[3];
}
}
for(int i=0;i<=1024;++i)
for(int j=0;j<=1024;++j)
f[i][j]=node(-1,-1);
node ans=dp(1,0); //cout<<flag<<endl;
if(flag) cout<<"-1"<<endl;
else cout<<ans.cnt<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 20080kb
input:
1 HALT; PUSH 1 GOTO 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 5ms
memory: 20300kb
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: 0ms
memory: 20140kb
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: 5ms
memory: 20188kb
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'