QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#505159#2833. HamiltonxiaohuzaiRE 0ms3828kbC++142.1kb2024-08-04 20:53:162024-08-04 20:53:17

Judging History

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

  • [2024-08-04 20:53:17]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3828kb
  • [2024-08-04 20:53:16]
  • 提交

answer

#include<bits/stdc++.h>
#define gt getchar
#define pt putchar
#define fst first
#define scd second
typedef long long ll;
using namespace std;
const int N=2005;
typedef pair<int,int> pii;
inline bool __(char ch){return ch>=48&&ch<=57;}
template<class T> inline void read(T &x){
	x=0;bool sgn=0;char ch=gt();
	while(!__(ch)&&ch!=EOF) sgn|=(ch=='-'),ch=gt();
	while(__(ch)) x=(x<<1)+(x<<3)+(ch&15),ch=gt();
	if(sgn) x=-x;
}
template<class T,class ...T1> inline void read(T &x,T1 &...x1){
	read(x);
	read(x1...);
}
template<class T> inline void print(T x){
	static char st[70];short top=0;
	if(x<0) pt('-');
 	do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
    while(top) pt(st[top--]);
}
template<class T> inline void printsp(T x){
	print(x);
	putchar(' ');
}
template<class T> inline void println(T x){
	print(x);
	putchar('\n');
}
bool a[N][N];
int nxt[N],st,pre[N];
void solve(int n){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			char ch;cin>>ch;
			a[i][j]=ch-'0';
		}
	}
	for(int i=0;i<=n;i++)nxt[i]=0,pre[i]=0;
	int now=1,st=1;
	nxt[1]=2,nxt[2]=1;
	pre[2]=1;pre[1]=2; 
	for(int i=3;i<=n;i++){
		if(now==1){ 
			nxt[i]=nxt[st];pre[nxt[st]]=i;
			if(a[i][nxt[i]]!=a[st][i])now=2;
			nxt[st]=i;pre[i]=st;
		}
		else{
			int nw=st,ck=0; 
			while(nw!=st){
				if(a[pre[nw]][nw]==0&&a[nw][nxt[nw]]==1){
					if(a[i][nw]==1){
						nxt[pre[nw]]=i,pre[i]=pre[nw];
						nxt[i]=nw,pre[nw]=i;
					}
					else{
						pre[nxt[nw]]=i,nxt[i]=nxt[nw];
						nxt[nw]=i,pre[i]=nw;	
					}
					ck=1;
				}
				nw=nxt[nw];
			} 
			if(!ck)assert(0); 
		}
	} 
	//for(int i=1;i<=n;i++)cout<<pre[i]<<" "<<nxt[i]<<endl; 
	for(int i=1;i<=n;i++){	
		int ck=0,ck1=0,nw=-1;
		st=i; 
		while(st!=i||nw==-1){
			nw=0;
			if(ck&&a[st][nxt[st]]==0){ck=1,ck1=-1;break;}
			if(a[st][nxt[st]]==1)ck=1;
			st=nxt[st]; 
		} 
		if(ck1==0){
			st=i;nw=-1;
			while(st!=i||nw==-1){
				nw=0;
				printsp(st);
				st=nxt[st];
			}
			cout<<endl;
			return;
		}
	}
	assert(0);
} 
int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
	//cin>>n;
		solve(n);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3704kb

input:

3
001
000
100
4
0000
0000
0000
0000

output:

3 2 1 
1 4 3 2 

result:

ok 2 cases.

Test #2:

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

input:

3
000
000
000
3
010
100
000
3
011
100
100
3
011
101
110

output:

1 3 2 
1 3 2 
3 2 1 
1 3 2 

result:

ok 4 cases.

Test #3:

score: -100
Runtime Error

input:

4
0000
0000
0000
0000
4
0000
0001
0000
0100
4
0100
1010
0100
0000
4
0111
1000
1000
1000
4
0010
0011
1101
0110
4
0111
1011
1100
1100
4
0111
1011
1101
1110
4
0000
0011
0101
0110
4
0101
1010
0100
1000
4
0011
0011
1100
1100
4
0010
0001
1000
0100

output:

1 4 3 2 
1 4 3 2 

result: