Submission #573948

#	Time	Username	Problem	Language	Result	Execution time	Memory
573948		WongChun1234	Mars (APIO22_mars)	C++17	100 / 100	1278 ms	5356 KiB

mars

#include "mars.h"
#include<bits/stdc++.h>
using namespace std;

const bool DEBUG=0;

bool board[50][50];
int clr[50][50];
vector<pair<int,int>> adj[50][50];

int X,Y,N,dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};

bool ok(int x,int y){
	return (x>=X&&x<=2*N&&y>=Y&&y<=2*N);
}

void dfs(int x,int y,int pt){
	clr[x][y]=pt;
	if (DEBUG) cerr<<"dfs"<<x<<","<<y<<":"<<pt<<"\n";
	for (int i=0;i<4;i++){
		if (!ok(x+dx[i],y+dy[i])) continue;
		if (clr[x+dx[i]][y+dy[i]]) continue;
		if (!board[x+dx[i]][y+dy[i]]) continue;
		dfs(x+dx[i],y+dy[i],pt);
	}
	for (auto i:adj[x][y]){
		if (clr[i.first][i.second]) continue;
		dfs(i.first,i.second,pt);
	}
}

string process(vector <vector<string>> a, int x, int y, int k, int n)
{
	string ret(100,'0');
	bool lbord=(x==2*(n-k-1)),rbord=(y==2*(n-k-1));
	memset(board,0,sizeof(board));
	X=x; Y=y; N=n;
	if (lbord&&rbord){
		//corner cell
		for (int i=0;i<=2;i++) for (int j=0;j<=2;j++) board[x+i][y+j]=a[i][j][0]=='1';
		for (int i=0;i<=1;i++) for (int dy=0,j=y+2;j<=2*n;j++,dy++) board[x+i][j]=(a[i][2][dy]=='1');
		for (int i=0;i<=1;i++) for (int dy=0,j=x+2;j<=2*n;j++,dy++) board[j][y+i]=(a[2][i][dy]=='1');
		for (int dy=51,j=y+3;j<=2*n;j++,dy++) board[x+2][j]=(a[1][2][dy]=='1');
		for (int dx=51,i=x+3;i<=2*n;i++,dx++) board[i][y+2]=(a[2][1][dx]=='1');
		ret[0]=a[0][0][0];
		vector<pair<int,int>> coord,stk;
		coord.clear(); stk.clear();
		for (int i=0;i<50;i++) for (int j=0;j<50;j++) adj[i][j].clear();
		for (int i=2*n;i>=x+2;i--) if (board[i][y+2]&&!board[i+1][y+2]) coord.push_back({i,y+2});
		for (int j=x+3;j<=2*n;j++) if (board[x+2][j]&&!board[x+2][j-1]) coord.push_back({x+2,j});
		for (int i=11,dx=0;dx<coord.size();i+=2,dx++){
			if (a[2][2][i]=='1'){
				cerr<<stk.back().first<<","<<stk.back().second<<"<->"<<coord[dx].first<<","<<coord[dx].second<<"\n";
				adj[stk.back().first][stk.back().second].push_back(coord[dx]);
				adj[coord[dx].first][coord[dx].second].push_back(stk.back());
				stk.pop_back();
			}
			if (a[2][2][i+1]=='1'){
				stk.push_back(coord[dx]);
			}
		}
		int pt=0,pt2=0,lpos[200],lval=0;
		memset(clr,0,sizeof(clr)); memset(lpos,0,sizeof(lpos));
		for (int i=2*n;i>=x;i--) for (int j=y;j<=2*n;j++){
			if (clr[i][j]) continue;
			if (!board[i][j]) continue;
			++pt;
			dfs(i,j,pt);
		}
		for (int i=2*n;i>=x;i--) if (board[i][y]&&!board[i+1][y]){
			pt2++;
			if (lpos[clr[i][y]]) ret[10+2*lpos[clr[i][y]]]='1',ret[10+2*pt2-1]='1';
			lpos[clr[i][y]]=pt2;
		}
		for (int j=y+1;j<=2*n;j++) if (board[x][j]&&!board[x][j-1]){
			pt2++;
			if (lpos[clr[x][j]]) ret[10+2*lpos[clr[x][j]]]='1',ret[10+2*pt2-1]='1';
			lpos[clr[x][j]]=pt2;
		}
		for (int i=1;i<=10;i++) lval+=(a[2][2][i]=='1')<<(i-1);
		for (int i=1;i<=pt;i++) if ((!lpos[i])||(!x)) lval++;
		for (int i=1;i<=10;i++) ret[i]='0'+((lval>>(i-1))&1);
		if (!x){
			for (int i=0;i<10;i++) ret[i]=ret[i+1];
			for (int i=10;i<100;i++) ret[i]='0';
		}
		if (DEBUG){
			cerr<<x<<" "<<y<<" at turn "<<k<<":"<<lval<<"\n";
			for (int i=0;i<=2*n;i++){
				for (int j=0;j<=2*n;j++) cerr<<board[i][j]<<" ";
				cerr<<"\n";
			}
			for (int i=0;i<=2*n;i++){
				for (int j=0;j<=2*n;j++) cerr<<clr[i][j]<<" ";
				cerr<<"\n";
			}
		}
	}else if (lbord){
		ret[0]=a[0][0][0]; ret[1]=a[1][0][0];
		for (int i=x+2;i<=2*n;i++) ret[i-x]=a[2][0][i-x-2];
		if (y+1==2*(n-k-1)){
			ret[51]=a[1][1][0];
			for (int i=x+2;i<=2*n;i++) ret[i-x+50]=a[2][1][i-x-2];
		}
	}else if (rbord){
		ret[0]=a[0][0][0]; ret[1]=a[0][1][0];
		for (int j=y+2;j<=2*n;j++) ret[j-y]=a[0][2][j-y-2];
		if (x+1==2*(n-k-1)){
			ret[51]=a[1][1][0];
			for (int j=y+2;j<=2*n;j++) ret[j-y+50]=a[1][2][j-y-2];
		}
	}else ret=a[0][0];
	return ret;
}
/*
1
2
1 0 0 1 0
1 1 0 1 0
1 1 0 0 1
0 0 1 0 1
0 0 0 1 0
*/

Compilation message (stderr)

mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:51:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int i=11,dx=0;dx<coord.size();i+=2,dx++){
      |                      ~~^~~~~~~~~~~~~

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