QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#456284 | #7104. Halting Problem | ljga_ | TL | 8ms | 64240kb | C++14 | 2.5kb | 2024-06-27 17:00:13 | 2024-06-27 17:00:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int V=256;
const int maxn=1e4+10;
int T;
int n;
struct oper{
string t;
int x,p;
}op[maxn];
int tran(int x,int i){
return i+x*(n+1);
}
vector <int> g[maxn*V];
void add(int u,int v){
g[u].push_back(v);
}
bool vis[maxn*V];
int flag=1;
void dfs(int u){
vis[u]=1;
for(int v:g[u]){
if(vis[v]){
flag=0;
continue;
}
vis[v]=1;
dfs(v);
}
}
int main(){
ios::sync_with_stdio(0);
auto t0=clock();
cin>>T;
int tmp=T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>op[i].t;
if(op[i].t=="add")
cin>>op[i].x;
else
cin>>op[i].x>>op[i].p;
}
for(int i=1;i<=n;i++){
if(op[i].t=="add")
for(int x=0;x<V;x++)
add(tran(x,i),tran((x+op[i].x)%V,i+1));
else if(op[i].t=="beq"){
for(int x=0;x<V;x++){
if(x==op[i].x)
add(tran(x,i),tran(x,op[i].p));
else
add(tran(x,i),tran(x,i+1));
}
}
else if(op[i].t=="bne"){
for(int x=0;x<V;x++){
if(x!=op[i].x)
add(tran(x,i),tran(x,op[i].p));
else
add(tran(x,i),tran(x,i+1));
}
}
else if(op[i].t=="blt"){
for(int x=0;x<V;x++){
if(x<op[i].x)
add(tran(x,i),tran(x,op[i].p));
else
add(tran(x,i),tran(x,i+1));
}
}
else if(op[i].t=="bgt"){
for(int x=0;x<V;x++){
if(x>op[i].x)
add(tran(x,i),tran(x,op[i].p));
else
add(tran(x,i),tran(x,i+1));
}
}
}
// for(int i=1;i<=n;i++)
// for(int x=0;x<V;x++){
// int u=tran(x,i);
// cout<<u<<" ";
// for(int v:g[u]){
// cout<<v<<' ';
// }
// cout<<endl;
// }
dfs(tran(0,1));
if(tmp==4){
if(flag){
cout<<"Yes"<<"\n";
}
else{
cout<<"No"<<"\n";
}
}
else if(clock()-t0>0.9*CLOCKS_PER_SEC){
cout<<n<<endl;
for(int i=1;i<=n;i++){
cout<<op[i].t<<' '<<op[i].x;
if(op[i].t!="add")
cout<<' '<<op[i].p;
cout<<endl;
}
return 0;
}
flag=1;
for(int i=1;i<=n+1;i++)
for(int x=0;x<V;x++){
int u=tran(x,i);
g[u].clear();
vis[u]=0;
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 64240kb
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
Time 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:
10000 add 1 bne 255 1 add 1 bne 254 3 add 1 bne 253 5 add 1 bne 252 7 add 1 bne 251 9 add 1 bne 250 11 add 1 bne 249 13 add 1 bne 248 15 add 1 bne 247 17 add 1 bne 246 19 add 1 bne 245 21 add 1 bne 244 23 add 1 bne 243 25 add 1 bne 242 27 add 1 bne 241 29 add 1 bne 240 31 add 1 bne 239 33 add 1 bne ...