QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#456284#7104. Halting Problemljga_TL 8ms64240kbC++142.5kb2024-06-27 17:00:132024-06-27 17:00:14

Judging History

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

  • [2024-06-27 17:00:14]
  • 评测
  • 测评结果:TL
  • 用时:8ms
  • 内存:64240kb
  • [2024-06-27 17:00:13]
  • 提交

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 ...

result: