QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#505159 | #2833. Hamilton | xiaohuzai | RE | 0ms | 3828kb | C++14 | 2.1kb | 2024-08-04 20:53:16 | 2024-08-04 20:53:17 |
Judging History
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