rt,数据下下来本地秒出,洛谷全TLE?为什么啊(((
#include <bits/stdc++.h>
struct stack {
int the_stack[501],sum=0;
inline int top() { return the_stack[sum-1]; }
inline int pop() { return sum ? the_stack[--sum] : -1; }
inline int push(int x) { the_stack[sum++]=x; }
inline int operator[](const int &x) const{
return the_stack[x-1];
}
inline void clear() { sum=0; }
}st;
inline long long read() {
long long x;bool f;char ch;
for(f=0;!isdigit(ch=getchar());f=ch=='-');
for(x=ch-48;isdigit(ch=getchar());x=x*10+ch-48);
return f?-x:x;
}
inline void print(long long x,char las) {
if(!x) {
putchar(48),putchar(las);
return ;
}
if(x<0) putchar('-'),x=-x;
int ls[20],k=0;
while(x) ls[++k]=x%10,x/=10;
while(k) putchar(ls[k--]+48);
putchar(las);
return ;
}
struct node {
node *left,*right,*down,*up,*col;int row,sum;
}nd[5001],head,c[501];
int n=read(),m=read(),cnt;
inline void delet(node *c) {
// return ;
c->right->left=c->left;c->left->right=c->right;
for(node *i=c->down;i!=c;i=i->down) {
for(node *j=i->right;j!=i;j=j->right) {
j->down->up=j->up;j->up->down=j->down;j->col->sum--;
}
}
return ;
}
inline void recover(node *c) {
// return ;
for(node *i=c->down;i!=c;i=i->down) {
for(node *j=i->right;j!=i;j=j->right) {
j->down->up=j->up->down=j;j->col->sum++;
}
}
c->right->left=c->left->right=c;
return ;
}
int ss;
inline bool dancing() {
if(head.right==&head) {
return true;
}
node *del=head.right;
for(node *i=del;i!=&head;i=i->right) if(i->sum<del->sum) del=i;
delet(del);
// ss--;
for(node *i=del->down;i!=del;i=i->down) {
st.push(i->row);
for(node *j=i->right;j!=i;j=j->right) delet(j->col)/*,ss--*/;
// print(ss,'\n');
if(dancing()) return true;
st.pop();
for(node *j=i->right;j!=i;j=j->right) recover(j->col)/*,ss++*/;
}
// ss++;
recover(del);
return false;
}
inline void solve() {
if(dancing()) {
while(st.sum) print(st.pop(),' ');
}else puts("No Solution!");
return ;
}
int main() {
ss=m;
head.right=&c[1];head.left=&c[m];
for(int i=1;i<=m;i++) c[i].right=&c[i+1],c[i].left=&c[i-1],c[i].up=c[i].down=&c[i];
c[1].left=c[m].right=&head;
for(int i=1;i<=n;i++) {
node *ls=0;
for(int j=1;j<=m;j++) {
int now=read();
if(now) {
c[j].sum++;
if(!ls) {
nd[++cnt].left=&nd[cnt];nd[cnt].right=&nd[cnt];
ls=&nd[cnt];
}else nd[++cnt].left=ls->left,nd[cnt].right=ls,ls->left->right=&nd[cnt],ls->left=&nd[cnt];
nd[cnt].row=i;nd[cnt].col=&c[j];
nd[cnt].up=c[j].up;nd[cnt].down=&c[j];c[j].up->down=&nd[cnt];c[j].up=&nd[cnt];
}
}
}
/*for(node *i=head.right;i!=&head;i=i->right) {
print(i-c,' ');
}*/
/*for(int i=1;i<=m;i++) {
for(node *j=c[i].down;j!=&c[i];j=j->down) {
print(j->row,' ');
}
puts("");
}*/
solve();
return 0;
}