警钟敲烂 (针对0分)
查看原帖
警钟敲烂 (针对0分)
37789
wutiruo楼主2022/10/2 22:42

不知道别人会不会和我犯同样的错。

/*
ID: wangjun30
LANG: C++11
TASK:
*/
// Code by Wutiruo

//Optimizers
//#pragma GCC optimize(2,3,"Ofast","-fgcse","-fgcse-lm","-fipa-sra","-ftree-pre","-ftree-vrp","-fpeephole2","-ffast-math","-fsched-spec","unroll-loops","-falign-jumps","-falign-loops","-falign-labels","-fdevirtualize","-fcaller-saves","-fcrossjumping","-fthread-jumps","-funroll-loops","-freorder-blocks","-fschedule-insns","inline-functions","-ftree-tail-merge","-fschedule-insns2","-fstrict-aliasing","-falign-functions","-fcse-follow-jumps","-fsched-interblock","-fpartial-inlining","no-stack-protector","-freorder-functions","-findirect-inlining","-fhoist-adjacent-loads","-frerun-cse-after-loop","inline-small-functions","-finline-small-functions","-ftree-switch-conversion","-foptimize-sibling-calls","-fexpensive-optimizations","inline-functions-called-once","-fdelete-null-pointer-checks","inline","fast-math","unroll-loops")
//#pragma GCC target("sse3","sse2","sse","avx","sse4","sse4.1","sse4.2","ssse3","f16c")
//#pragma GCC diagnostic error "-fwhole-program","-fcse-skip-blocks","-funsafe-loop-optimizations","-std=c++14"
//Only the last two lines are available on luogu

//Main Code
#include<bits/stdc++.h>
using namespace std;

//#include<bits/extc++.h>
//using namespace __gnu_cxx;
//Note: this header can't be used in Dev-C++

#define ll long long

namespace FastIO_fread{
	char buf[4194304],*p1=buf,*p2=buf,pbuf[4194304],*pp=pbuf;
	inline char gc()
	{
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,4194304,stdin),p1==p2)?EOF:*p1++;
	}
	inline int read()
	{
		int x=0;
		char ch=gc(),flag=0;
		while(ch<'0'||ch>'9')
			flag|=(ch=='-'),ch=gc();
		while(ch>='0'&&ch<='9')
			x=(x<<3)+(x<<1)+ch-'0',ch=gc();
		return flag?~x+1:x;
	}
	inline void push(char c)
	{
		if(pp-pbuf==4194304)
			fwrite(pbuf,1,4194304,stdout),pp=pbuf;
		*pp++=c;
	}
	inline void write(int x)
	{
		static int sta[20];
		int top=0;
		if(x<0)
			push('-'),x=-x;
		do
			sta[top++]=x%10,x/=10;
		while(x);
		while(top)
			push(sta[--top]+'0');
	}
	void flush()
	{
		fwrite(pbuf,pp-pbuf,1,stdout);
	}
}
//using namespace FastIO_fread;

int _LINE_R[1010];
#define assert_line(n) {_LINE_R[__LINE__]++;assert(_LINE_R[__LINE__]<=n);}

//(){}0[]
struct DLXNode{
	int left,right,down,up;
	int row,col;
}DLX[6010];
typedef DLXNode DLXN;
DLXN &head=DLX[0];
int ccnt[510];//colomn's elements cnt
int rows[510];//row's first element
int ans[510];//answer
int tot,n,m;
enum PlaceType{
	_up=1,
	_down=2,
	_left=3,
	_right=4
};
void add_node(const int &r,const int &c){
	DLX[++tot].up=DLX[c].up;
	DLX[tot].down=c;
	DLX[DLX[tot].up].down=tot;
	DLX[c].up=tot;

	if(!rows[r]){
		DLX[tot].left=tot;
		DLX[tot].right=tot;
		rows[r]=tot;
	}
	else{
		DLX[tot].right=rows[r];
		DLX[tot].left=DLX[rows[r]].left;
		DLX[rows[r]].left=tot;
		DLX[DLX[tot].left].right=tot;
	}

	ccnt[c]++;
	
	DLX[tot].row=r;
	DLX[tot].col=c;
}

namespace DLXPrintf{
	char ch[510][510];
	char Data[15][15];
	void PrintDLXf(){
		memset(ch,' ',sizeof ch);
		memset(Data,0,sizeof Data);
		string str;
		cerr<<"DLX state formated input: (For debug)\n";
		Data[0][0]='H';
		for(int i=head.right;i;i=DLX[i].right){
			Data[0][i]=i+48;
			for(int j=DLX[i].down;j!=i;j=DLX[j].down)
				Data[DLX[j].row][DLX[j].col]='T';
		}
		for(int i=1;i<=n+1;i++)
			for(int j=0;j<4*(m+2)-1;j++)
				ch[i*4-1][j]='-';
		for(int i=2;i<=m+1;i++)
			for(int j=0;j<4*(n+2)-1;j++)
				if(ch[j][i*4-1]==' ')
					ch[j][i*4-1]='|';
				else
					ch[j][i*4-1]='+';
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
				if(Data[i][j])
					ch[(i+1)*4-1][(j+1)*4-1]=Data[i][j];
		for(int i=1;i<=n+1;i++){
			bool flag=true;
			for(int j=0;j<4*(m+2)-1;j++)
				if(isalpha(ch[i*4-1][j]) or isdigit(ch[i*4-1][j]))
					flag=false;
			if(flag){
				for(int j=0;j<4*(m+2)-1;j++)
					if(ch[i*4-1][j]=='-')
						ch[i*4-1][j]=' ';
					else if(ch[i*4-1][j]=='+')
						ch[i*4-1][j]='|';
			}
		}
		for(int i=1;i<=m+1;i++){
			bool flag=true;
			for(int j=0;j<4*(n+2)-1;j++)
				if(isalpha(ch[j][i*4-1]) or isdigit(ch[j][i*4-1]))
					flag=false;
			if(flag){
				for(int j=0;j<4*(n+2)-1;j++)
					if(ch[j][i*4-1]=='|')
						ch[j][i*4-1]=' ';
					else if(ch[j][i*4-1]=='+')
						ch[j][i*4-1]='-';
			}
		}
		for(int i=1;i<(n+2)*4-1;i++){
			ch[i][(m+2)*4]='\n';
			ch[i][(m+2)*4+1]='\0';
			cerr<<ch[i];
		}
		cerr<<'\n';
	}
	void PrintDLX(){
		/*Reserved*/
	}
}
using DLXPrintf::PrintDLXf;
using DLXPrintf::PrintDLX;

int _i,_j,_c,_k;
void Remove(int &c){
	for(int i=DLX[c].down;i!=c;i=DLX[i].down)
		for(int j=DLX[i].right;j!=i;j=DLX[j].right){
			DLX[DLX[j].up].down=DLX[j].down;
			DLX[DLX[j].down].up=DLX[j].up;
			ccnt[DLX[j].col]--;
		}
	DLX[DLX[c].left].right=DLX[c].right;
	DLX[DLX[c].right].left=DLX[c].left;
}
void Resume(int &c){
	DLX[DLX[c].left].right=c;
	DLX[DLX[c].right].left=c;
	for(int i=DLX[c].down;i!=c;i=DLX[i].down)
		for(int j=DLX[i].right;j!=i;j=DLX[j].right){
			DLX[DLX[j].up].down=j;
			DLX[DLX[j].down].up=j;
			ccnt[DLX[j].col]++;
		}
}
void dance(int dep){
	if(head.right==0){
		for(int i=1;i<dep;i++)
			cout<<ans[i]<<' ';
		cout<<flush;
		exit(0);
	}
	int col=head.right,cs;
	for(int i=head.right;i;i=DLX[i].right)
		if(ccnt[i]<ccnt[col])
			col=i;
	PrintDLX();
	Remove(col);
	PrintDLX();
	cs=DLX[col].down;
   if(cs==col)
   		return;
        //这个地方挂了两个小时,直接return了没有resume col这一列,大红大紫,还不知道哪里错了
	while(cs!=col){
		ans[dep]=DLX[cs].row;
		PrintDLX();
		for(int j=DLX[cs].right;j!=cs;j=DLX[j].right)
			Remove(DLX[j].col);
		PrintDLX();
		dance(dep+1);
		for(int j=DLX[cs].right;j!=cs;j=DLX[j].right)
			Resume(DLX[j].col);
		cs=DLX[cs].down;
	}
	Resume(col);
}
void Init(){
	tot=m;
	head.right=1;
	head.left=m;
	for(int i=1;i<=m;i++){
		DLX[i].left=i-1;
		DLX[i].right=i+1;
		DLX[i].up=i;
		DLX[i].down=i;
		DLX[i].col=i;
	}
	DLX[m].right=0;
}
void Input(){
	{
		for(int i=1,tmp;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>tmp;
				if(tmp)
					add_node(i,j);
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	Init();
	Input();
	dance(1);
	cout<<"No Solution!"<<flush;
	return 0;
}
/*
6 7
0 0 1 1 0 1 0
1 0 0 0 1 0 1
0 1 1 0 0 1 0
1 0 0 0 1 0 0
0 1 0 0 0 0 1
0 1 0 1 1 0 1
*/
2022/10/2 22:42
加载中...