Submission #745284

#	Time	Username	Problem	Language	Result	Execution time	Memory
745284		speedyArda	Mars (APIO22_mars)	C++17	36 / 100	173 ms	3048 KiB

mars

#include<bits/stdc++.h>
#include"mars.h"
using namespace std;
int const N=2333,dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int f[N];
int find(int x){
	return f[x]^x?f[x]=find(f[x]):x;
}
void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx^fy)f[fx]=fy;
}
int ord(int x,int y,int n){
	return x*n+y;
}
string solve(vector<vector<string>>const&a,int n){
	string s=string(N,48);
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			for(int x=0;x<n/2;x++)
				for(int y=0;y<n/2;y++)
					s[ord(i+x*2,j+y*2,n)]=a[i][j][ord(x,y,n/2)];
	//rebuild the whole graph
	for(int i=0;i<n*n;i++)
		if(s[i]==49)f[i]=i;
	for(int x=0;x<n;x++)
		for(int y=0;y<n;y++)
			for(int i=0;i<4;i++){
				int tx=x+dx[i],ty=y+dy[i],p1=ord(x,y,n),p2=ord(tx,ty,n);
				if(tx<0||tx>=n||ty<0||ty>=n||s[p1]==48||s[p2]==48)continue;
				merge(p1,p2);
			}
	int cnt=0;
	for(int i=0;i<n*n;i++)
		cnt+=s[i]==49&&find(i)==i;
	//use dsu to count the answer
	string res=string(100,48);
	for(int i=0;cnt;i++)
		res[i]+=cnt&1,cnt>>=1;
	return res;
}
string process(vector<vector<string>>a,int ti,int tj,int k,int n){
	string s=string(100,48);
	if(k==n-1)
		return solve(a,2*n+1);
	for(int i=0;i<3;i+=2)
		for(int j=0;j<3;j+=2)
			for(int x=0;x<=k;x++)
				for(int y=0;y<=k;y++)
					s[ord(x+i/2,y+j/2,k+2)]=a[i][j][ord(x,y,k+1)];
	//(x,y) stores the info of (x+2i,y+2j) instead of (x+i,y+j) (i,j\in N)
	return s;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 0 / 8
• Subtask 7: 0 / 10
• Subtask 8: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11