提出 #40300691

---

ソースコード 拡げる

//This code is written by hmz,and hmz is cute!!!
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define TY long long
#define umap unordered_map
#define ull unsigned long long
#define pq priority_queue
#define Open(a) [a.x][a.y][a.z]
#define mp make_pair
#define mod (TY)(1e9+7)
#define MAXN 15
#define MAXM 15*15*15*15
#define MAXK 27
#define INF (TY)1e9
#define Read(name) freopen(#name,"r",stdin);
#define Write(name) freopen(#name,"w",stdout);
#define For(i,a,b) for(TY i=(a);i<=(b);++i)
#define FOR(i,a,b) for(TY i=(a);i<(b);++i)
#define Rof(i,a,b) for(TY i=(a);i>=(b);--i)
#define ROF(i,a,b) for(TY i=(a);i>(b);--i)
inline TY qr(){
	TY x=0,f=1;char op=getchar();
	for(;op<'0'||op>'9';op=getchar())if(op=='-')f=-1;
	for(;op>='0'&&op<='9';op=getchar())x=x*10+(op^48);
	return x*f;
}inline char getc(){
	char op=getchar();
	while(op==' '||op=='\n'||op=='\r')op=getchar();
	return op;
}inline string qs(){
	string op="";char u=getchar();
	while(u=='\n'||u=='\r'||u==' ')u=getchar();
	while(u!='\n'&&u!='\r'&&u!=' ')op+=u,u=getchar();
	return op;
}inline void qw(TY x){
	if(!x){putchar('0');return;}
	if(x<0)putchar('-'),x=-x;
	if(x>=10)qw(x/10);putchar(x%10+'0');
}inline void qw(TY x,char op){qw(x),putchar(op);}
inline void ws(string s){FOR(i,0,s.size())putchar(s[i]);}
inline TY Ceil(TY a,TY b){return a/b+(a%b!=0);}
inline TY Mod(TY a){return (a>=mod?a-mod:a);}
inline TY Abs(TY a,TY b){return a>b?a-b:b-a;}
inline TY Pow(TY a,TY b){
	TY ans=1,base=a;
	while(b){
		if(b&1)ans=ans*base%mod;
		base=base*base%mod;b>>=1;
	}return ans;
}TY n,lstc,allcnt,tot=1,cnt[2],lstcnt[2],lstnum[2][MAXM],ans[2][MAXN][MAXN][MAXN];
TY need[2][MAXN][MAXN][MAXN],Merg[2][MAXN][MAXN][MAXN],id[2][MAXN][MAXN][MAXN],h[MAXM];
struct edge{TY u,v,w;};inline bool cmp(edge x,edge y){return x.w<y.w;}
struct Point{
	TY x,y,z;
	inline bool operator==(const Point& A) const{
		return x==A.x&&y==A.y&&z==A.z;
	}inline bool operator!=(const Point& A) const{
		return x!=A.x||y!=A.y||z!=A.z;
	}
};char a[4][MAXN][MAXN];mt19937 rnd(0);bool alrrun[MAXM];
inline bool Cmp(Point x,Point y){return x.x!=y.x?x.x<y.x:x.y!=y.y?x.y<y.y:x.z<y.z;}
inline bool CMP(const vector<Point>& x,const vector<Point>& y){return x.size()<y.size();}
vector<edge> have[2];queue<TY> q;vector<Point> Set[2][MAXM];
TY S,T,pre[MAXM<<1],dis[MAXM<<1],head[MAXM<<1],lst[MAXM<<1],len[MAXM<<1];bool vis[MAXM<<1];
const TY dc[6][3]={{-1,0,0},{1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
const TY B[3][2]={{0,1},{2,3},{4,5}};TY beg[4]={1,2,3,4},lstSX[4]={2,1,3,4};double minnans=1e9;
struct node{TY y,nex,w,dis;}s[MAXM<<3];
inline void lstOutput(){
	cnt[0]=cnt[1]=0;
	TY lstcc=0;
	For(op,0,1)FOR(i,0,n)FOR(j,0,n)FOR(k,0,n){
		cnt[op]=max(cnt[op],ans[op][i][j][k]);
	}For(op,0,1)FOR(i,0,n)FOR(j,0,n)FOR(k,0,n){
		if(need[op][i][j][k]&&!ans[op][i][j][k])ans[op][i][j][k]=++cnt[op];
	}lstcc=max(cnt[0],cnt[1]);
	qw(lstcc,'\n');For(op,0,1){
		FOR(i,0,n)FOR(j,0,n)FOR(k,0,n)qw(ans[op][i][j][k],' ');
		putchar('\n');
	}exit(0);
}inline void ChangeID(){
	TY cc=0;For(op,0,1)FOR(i,0,n)FOR(j,0,n)FOR(k,0,n){
		if(ans[op][i][j][k])h[++cc]=ans[op][i][j][k];
	}sort(h+1,h+1+cc);cc=unique(h+1,h+1+cc)-h-1;
	For(op,0,1)FOR(i,0,n)FOR(j,0,n)FOR(k,0,n){
		if(ans[op][i][j][k]<=0)ans[op][i][j][k]=0;
		else ans[op][i][j][k]=lower_bound(h+1,h+1+cc,ans[op][i][j][k])-h;
	}
}inline void clear(){
	allcnt=lstc=0;tot=1;cnt[0]=cnt[1]=lstcnt[0]=lstcnt[1]=0;
	memset(lstnum,0,sizeof(lstnum));
	memset(ans,0,sizeof(ans));memset(need,0,sizeof(need));
	memset(Merg,0,sizeof(Merg));memset(id,0,sizeof(id));
	memset(h,0,sizeof(h));have[0].clear();have[1].clear();
	S=T=0;memset(pre,0,sizeof(pre));
	memset(dis,0,sizeof(dis));memset(head,0,sizeof(head));
	memset(lst,0,sizeof(lst));memset(vis,0,sizeof(vis));
	memset(len,0,sizeof(len));memset(alrrun,0,sizeof(alrrun));
	For(op,0,1)FOR(i,0,MAXM)Set[op][i].clear();
}inline bool Next(const Point&x,const Point&y){return abs(x.x-y.x)+abs(x.y-y.y)+abs(x.z-y.z)==1;}
inline bool InMap(const Point&x){return x.x>=0&&x.x<n&x.y>=0&&x.y<n&&x.z>=0&&x.z<n;}
inline bool Belong(bool op,const Point&x,const Point&y){return ans[op]Open(x)==ans[op]Open(y)&&ans[op]Open(x)>0;}
inline TY GetVal(const Point&x){return x.x*n*n+x.y*n+x.z;}
inline Point Add(const Point&x,TY d){return {x.x+dc[d][0],x.y+dc[d][1],x.z+dc[d][2]};}
inline bool Same(const Point&a,const Point&b,const Point&c,const Point&d){
	if(a.x==b.x&&a.x==c.x&&a.x==d.x)return true;
	if(a.y==b.y&&a.y==c.y&&a.y==d.y)return true;
	if(a.z==b.z&&a.z==c.z&&a.z==d.z)return true;
	return false;
}inline Point FindNxt(bool op,const Point&fir){
	For(d,0,5){
		Point sec=Add(fir,d);
		if(InMap(sec)&&Belong(op,fir,sec)){
			return sec;
		}
	}
}inline TY TURN(const Point&x,const Point&y){
	if(x.x!=y.x)return 0;
	if(x.y!=y.y)return 1;
	return 2;
}inline bool Equal(vector<Point> fir,vector<Point> sec){
	if(fir.size()!=sec.size())return false;
	TY minx=1e9,miny=1e9,minz=1e9;
	FOR(i,0,fir.size())minx=min(minx,fir[i].x),miny=min(miny,fir[i].y),minz=min(minz,fir[i].z);
	FOR(i,0,fir.size())fir[i].x-=minx,fir[i].y-=miny,fir[i].z-=minz;
	sort(fir.begin(),fir.end(),Cmp);
	minx=miny=minz=1e9;
	FOR(i,0,sec.size())minx=min(minx,sec[i].x),miny=min(miny,sec[i].y),minz=min(minz,sec[i].z);
	FOR(i,0,sec.size())sec[i].x-=minx,sec[i].y-=miny,sec[i].z-=minz;
	sort(sec.begin(),sec.end(),Cmp);
	FOR(i,0,fir.size())if(fir[i]!=sec[i])return false;
	return true;
}inline vector<Point> Add(const vector<Point>&fir,const vector<Point>&sec){
	vector<Point> tmp=fir;
	FOR(i,0,sec.size())tmp.push_back(sec[i]);
	return tmp;
}inline void Del(bool op,TY a,TY b){
	FOR(i,0,Set[op][b].size())Set[op][a].push_back({Set[op][b][i]});
	Set[op][b].clear();
	FOR(i,b,lstc)Set[op][i]=Set[op][i+1];
}inline vector<Point> TURN(vector<Point> beg,TY a,TY b,TY c){
	FOR(i,0,beg.size()){
		For(j,1,a)swap(beg[i].x,beg[i].y),beg[i].x*=-1;
		For(j,1,b)swap(beg[i].x,beg[i].z),beg[i].z*=-1;
		For(j,1,c)swap(beg[i].y,beg[i].z),beg[i].y*=-1;
	}return beg;
}inline void Cover(bool op,const vector<Point>&a,TY w){
	FOR(i,0,a.size())ans[op]Open(a[i])=w;
}inline void allCover(bool op,TY a,TY b){
	FOR(i,0,n)FOR(j,0,n)FOR(k,0,n)if(ans[op][i][j][k]==a){
		ans[op][i][j][k]=b;
	}
}inline bool Nxt(const vector<Point>&a,const vector<Point>&b){
	FOR(i,0,a.size())FOR(j,0,b.size())if(Next(a[i],b[j]))return true;
	return false;
}inline bool TurnSame(const vector<Point>&fir,const vector<Point>&sec){
	For(a,0,3)For(b,0,3)For(c,0,3){
		if(a>=2&&b>=2&&c>=2)continue;
		if(Equal(TURN(fir,a,b,c),sec))return true;
	}return false;
}inline double Calc(){
	double sum=0;memset(len,0,sizeof(len));
	FOR(i,0,n)FOR(j,0,n)FOR(k,0,n)++len[ans[0][i][j][k]];
	FOR(i,1,MAXM)if(len[i]>0)sum+=1.0/len[i];
	return sum;
}inline void add(TY i,TY j,TY k,TY dis){
	s[++tot].y=j,s[tot].nex=head[i],s[tot].w=k,s[tot].dis=dis;
	head[i]=tot;swap(i,j);
	s[++tot].y=j,s[tot].nex=head[i],s[tot].w=0,s[tot].dis=-dis;
	head[i]=tot;
}inline bool spfa(){
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	q.push(S);dis[S]=0;while(!q.empty()){
		TY now=q.front();q.pop();vis[now]=0;
		for(TY i=head[now];i;i=s[i].nex){
			TY y=s[i].y;if(dis[y]>dis[now]+s[i].dis&&s[i].w){
				dis[y]=dis[now]+s[i].dis;
				pre[y]=now;lst[y]=i;
				if(!vis[y])vis[y]=1,q.push(y);
			}
		}
	}return dis[T]<1e16;
}inline TY dfs(TY now,TY in){
	if(now==T)return in;
	vis[now]=1;TY out=0;
	for(TY i=head[now];i&&in;i=s[i].nex){
		TY y=s[i].y;
		if(!vis[y]&&s[i].w&&dis[now]+s[i].dis==dis[y]){
			TY tmp=dfs(y,min(s[i].w,in));
			in-=tmp,out+=tmp;
			s[i].w-=tmp;s[i^1].w+=tmp;
		}
	}if(out)vis[now]=0;
	return out;
}inline void solve(){
	while(spfa()){
		memset(vis,0,sizeof(vis));
		dfs(S,1e9);
		/*
		TY now=T;while(now!=S){
			--s[lst[now]].w;
			++s[lst[now]^1].w;
			now=pre[now];
		}*/
	}
}inline void Maintain(){
	have[0].clear();have[1].clear();
	For(op,0,1)FOR(i,0,n)FOR(j,0,n)FOR(k,0,n){
		if(Merg[op][i][j][k]){
			Point fir={i,j,k},sec=FindNxt(op,fir);
			Merg[op]Open(fir)=Merg[op]Open(sec)=0;
			have[op].push_back({GetVal(fir),GetVal(sec),0});
		}
	}cnt[0]=cnt[1]=0;
	FOR(op,0,1)FOR(i,0,have[op].size()){
		TY a=have[0][i].u,b=have[0][i].v;
		TY c=have[1][i].u,d=have[1][i].v;
		ans[0][a/(n*n)][a%(n*n)/n][a%n]=ans[0][b/(n*n)][b%(n*n)/n][b%n]=++cnt[0];
		ans[1][c/(n*n)][c%(n*n)/n][c%n]=ans[1][d/(n*n)][d%(n*n)/n][d%n]=++cnt[1];
	}TY cc=0;For(op,0,1)FOR(i,0,n)FOR(j,0,n)FOR(k,0,n)if(ans[op][i][j][k]==0&&need[op][i][j][k]){
		ans[op][i][j][k]=++cnt[op];	
	}For(op,0,1)FOR(i,0,n)FOR(j,0,n)FOR(k,0,n){
		if(ans[op][i][j][k]>0)h[++cc]=ans[op][i][j][k];
	}sort(h+1,h+1+cc);cc=unique(h+1,h+1+cc)-h-1;lstc=cc;
	For(op,0,1)FOR(i,0,n)FOR(j,0,n)FOR(k,0,n){
		if(ans[op][i][j][k]>0)ans[op][i][j][k]=lower_bound(h+1,h+1+cc,ans[op][i][j][k])-h;
		else ans[op][i][j][k]=0;
	}For(op,0,1)FOR(i,0,n)FOR(j,0,n)FOR(k,0,n){
		Set[op][ans[op][i][j][k]].push_back({i,j,k});
	}
}inline void SA(){
	For(i,0,3)FOR(j,0,n)FOR(k,0,n){
		bool op=(i>=2);
		if(a[i][j][k]=='0'){
			FOR(w,0,n){
				if(i==1||i==3)ans[op][w][k][j]=-1;
				else ans[op][k][w][j]=-1;
			}
		}
	}For(i,0,3)FOR(j,0,n)FOR(k,0,n){
		bool op=(i>=2);
		if(a[i][j][k]=='1'){
			if(i==1||i==3){
				FOR(w,0,n){
					if(ans[op][w][k][j]!=-1){
						if(!need[op][w][k][j])need[op][w][k][j]=1;
						break;
					}
				}
			}else{
				Rof(w,n-1,0){
					if(ans[op][k][w][j]!=-1){
						if(!need[op][k][w][j])need[op][k][w][j]=1;
						break;
					}
				}
			}
		}
	}S=2*n*n*n+1,T=S+1;
	For(op,0,1)FOR(i,0,n)FOR(j,0,n)FOR(k,0,n){
		Point fir={i,j,k};
		if((i+j+k)%2==0&&ans[op]Open(fir)!=-1){
			add(S,GetVal(fir)+op*n*n*n,1,0);
			For(d,0,5){
				Point sec=Add(fir,d);TY cc;
				if(InMap(sec)&&ans[op]Open(sec)!=-1){
					if(!need[op]Open(fir)&&!need[op]Open(sec))cc=1001;
					else if(need[op]Open(fir)!=need[op]Open(sec))cc=1000;
					else cc=0;
					add(GetVal(fir)+op*n*n*n,GetVal(sec)+op*n*n*n,1,cc);
				}
			}
		}else if(ans[op]Open(fir)!=-1)add(GetVal(fir)+op*n*n*n,T,1,0);
	}solve();
	For(i,2,tot)if(i%2==0&&s[i].y!=S&&s[i].y!=T&&s[i].w==0&&s[i^1].y!=S&&s[i^1].y!=T){
		TY a=(s[i].y>=n*n*n?s[i].y-n*n*n:s[i].y);
		TY b=(s[i^1].y>=n*n*n?s[i^1].y-n*n*n:s[i^1].y);
		have[s[i].y>=n*n*n].push_back({a,b,s[i].dis});
	}sort(have[0].begin(),have[0].end(),cmp);
	sort(have[1].begin(),have[1].end(),cmp);
	FOR(i,0,min(have[0].size(),have[1].size())){
		TY a=have[0][i].u,b=have[0][i].v;
		TY c=have[1][i].u,d=have[1][i].v;
		if(have[0][i].w==1001&&have[1][i].w==1001)break;
		ans[0][a/(n*n)][a%(n*n)/n][a%n]=ans[0][b/(n*n)][b%(n*n)/n][b%n]=++cnt[0];
		Merg[0][a/(n*n)][a%(n*n)/n][a%n]=Merg[0][b/(n*n)][b%(n*n)/n][b%n]=1;
		ans[1][c/(n*n)][c%(n*n)/n][c%n]=ans[1][d/(n*n)][d%(n*n)/n][d%n]=++cnt[1];
		Merg[1][c/(n*n)][c%(n*n)/n][c%n]=Merg[1][d/(n*n)][d%(n*n)/n][d%n]=1;
	}Maintain();allcnt=max(cnt[0],cnt[1]);
}inline bool FindSame(TY ida,TY idb){
	vector<Point> need=Add(Set[0][ida],Set[0][idb]);
	TY A=ans[0]Open(Set[0][ida][0]),B=ans[0]Open(Set[0][idb][0]);
	For(i,1,lstc)For(j,1,lstc){
		if(i==j)continue;
		if(!TurnSame(Set[1][i],Set[0][ida])||!TurnSame(Set[1][j],Set[0][idb])||!Nxt(Set[1][i],Set[1][j]))continue;
		vector<Point> tmp=Add(Set[1][i],Set[1][j]);
		if(TurnSame(tmp,need)){
			TY fir=ans[1]Open(Set[1][i][0]),sec=ans[1]Open(Set[1][j][0]);
			allCover(0,fir,A);allCover(0,sec,B);
			Cover(1,Set[1][i],allcnt);
			Cover(1,Set[1][j],allcnt);
			Del(1,i,j);
			return true;
		}
	}return false;
}inline bool Merge(TY a,TY b){
	++allcnt;if(FindSame(a,b)){
		Cover(0,Set[0][a],allcnt);Cover(0,Set[0][b],allcnt);
		Del(0,a,b);--lstc;
		return true;
	}return false;
}inline void HMZ(){
	n=qr();
	For(i,0,3)FOR(j,0,n)FOR(k,0,n)a[i][j][k]=getc();
	SA();while(clock()*1.0/CLOCKS_PER_SEC<5.7){
		sort(Set[0]+1,Set[0]+1+lstc,CMP);
		bool vis=0;
		For(i,1,lstc){
			For(j,i+1,lstc){
				if(clock()*1.0/CLOCKS_PER_SEC>5.7)break;
				if(!Nxt(Set[0][i],Set[0][j]))continue;
				if(Merge(i,j)){vis=1;break;}
			}if(clock()*1.0/CLOCKS_PER_SEC>5.7)break;
		}
	}ChangeID();lstOutput();
}int main(){
	//Read(0000.txt);
	TY T=1;while(T--)HMZ();
	//cout<<"tim "<<clock()<<endl;
    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘void qw(long long int)’:
./Main.cpp:39:2: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   39 |  if(x>=10)qw(x/10);putchar(x%10+'0');
      |  ^~
./Main.cpp:39:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   39 |  if(x>=10)qw(x/10);putchar(x%10+'0');
      |                    ^~~~~~~
./Main.cpp: In function ‘void ws(std::string)’:
./Main.cpp:19:34: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   19 | #define FOR(i,a,b) for(TY i=(a);i<(b);++i)
      |                                  ^
./Main.cpp:41:26: note: in expansion of macro ‘FOR’
   41 | inline void ws(string s){FOR(i,0,s.size())putchar(s[i]);}
      |                          ^~~
./Main.cpp: In function ‘bool InMap(const Point&)’:
./Main.cpp:101:52: warning: suggest parentheses around comparison in operand of ‘&’ [-Wparentheses]
  101 | inline bool InMap(const Point&x){return x.x>=0&&x.x<n&x.y>=0&&x.y<n&&x.z>=0&&x.z<n;}
      |                                                 ~~~^~
./Main.cpp: In function ‘bool Equal(std::vector<Point>, std::vector<Point>)’:
./Main.cpp:19:34: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<Point>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   19 | #define FOR(i,a,b) for(TY i=(a);i<(b);++i)
      |                                  ^
./Main.cpp:124:2: note: in expansion of macro ‘FOR’
  124 |  FOR(i,0,fir.size())minx=min(minx,fir[i].x),miny=min(miny,fir[i].y),minz=min(minz,fir[i].z);
      |  ^~~
./Main.cpp:19:34: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<Point>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   19 | #define FOR(i,a,b) for(TY i=(a);i<(b);++i)
      |                         ...

ジャッジ結果