Submission #572777

#	Time	Username	Problem	Language	Result	Execution time	Memory
572777		benson1029	Mars (APIO22_mars)	C++17	100 / 100	1310 ms	8432 KiB

mars

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

int N;
int v[100][100];
int refId[100][100];
vector< pair<int,int> > refs[10000];
int newGrpId[100][100];
int grpId;
bool vis[100][100];
int freq[10000];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

bool valid(int x, int y) {
	return ((x>=0 && y>=0 && x<=2*N && y<=2*N) && (v[x][y] == 1 && !vis[x][y]));
}

void dfs(int x, int y) {
	newGrpId[x][y] = grpId;
	vis[x][y] = true;
	for(int i=0; i<4; i++) {
		if(valid(x+dx[i], y+dy[i])) {
			dfs(x+dx[i], y+dy[i]);
		}
	}
	if(refId[x][y]!=-1) {
		for(auto i:refs[refId[x][y]]) {
			if(valid(i.first, i.second)) dfs(i.first, i.second);
		}
	}
}

string inttobin(int v, int len) {
	string rv = "";
	for(int i=0; i<len; i++) {
		if((v>>i)%2) rv += "1";
		else rv += "0";
	}
	return rv;
}

std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{
	N = n;
	// case handling
	int m = 2*(n-k-1);
	if(i == m && j == m) {
		
		// find v
		for(int I=0; I<=2*n; I++) {
			for(int J=0; J<=2*n; J++) {
				v[I][J] = -1;
				refId[I][J] = -1;
				vis[I][J] = false;
			}
		}
		string d1 = a[1][0].substr(1, k*3);
		string d2 = a[2][0].substr(1, k*3);
		string r1 = a[0][1].substr(1, k*3);
		string r2 = a[0][2].substr(1, k*3);
		int ptr = 0;
		for(int I=i+3; I<=2*n; I+=2) {
			for(int J=j; J<=j+2; J++) {
				v[I][J] = d1[ptr] - '0';
				ptr++;
			}
		}
		ptr = 0;
		for(int I=i+4; I<=2*n; I+=2) {
			for(int J=j; J<=j+2; J++) {
				v[I][J] = d2[ptr] - '0';
				ptr++;
			}
		}
		ptr = 0;
		for(int J=j+3; J<=2*n; J+=2) {
			for(int I=i; I<=i+2; I++) {
				v[I][J] = r1[ptr] - '0';
				ptr++;
			}
		}
		ptr = 0;
		for(int J=j+4; J<=2*n; J+=2) {
			for(int I=i; I<=i+2; I++) {
				v[I][J] = r2[ptr] - '0';
				ptr++;
			}
		}
		for(int I=i; I<=i+2; I++) for(int J=j; J<=j+2; J++) v[I][J] = a[I-i][J-j][0] - '0';
		
		// decode previous string
		int ans = 0;
		
		if(k > 0) {
			string ansstr = a[2][2].substr(1, 10);
			for(int I=0; I<10; I++) {
				if(ansstr[I]=='1') ans += (1<<I);
			}
			
			vector< pair<int, int> > L; L.clear();
			vector< pair<int, int> > L2; L2.clear();
			vector<int> rel; rel.clear();
			
			for(int I=2*n; I>=i+2; I--) L.push_back({I, j+2});
			for(int J=j+3; J<=2*n; J++) L.push_back({i+2, J});
			
			int Prev = 0;
			int cnt = 0;
			for(auto c:L) {
				if(Prev == 0 && v[c.first][c.second] == 1) {
					refId[c.first][c.second] = cnt;
					L2.push_back(c);
					cnt++;
				}
				Prev = v[c.first][c.second];
			}
			
			string relstr = a[2][2].substr(11, 1e9); 
			stack<int> stk;
			
			int tmpcnt = -1;
			for(int I=0; I<relstr.length(); I++) {
				if(relstr[I] == '1') {
					if(tmpcnt+1 == cnt) break;
					tmpcnt++;
					stk.push(tmpcnt);
				} else {
					stk.pop();
					refId[L2[tmpcnt].first][L2[tmpcnt].second] = stk.top();
				}
			}
			
			for(int I=0; I<cnt; I++) refs[I].clear();
			for(auto c:L) {
				if(refId[c.first][c.second] != -1) {
					refs[refId[c.first][c.second]].push_back(c);
				}
			}
			
		}
		
		grpId = 0;
		for(int I=i; I<=2*n; I++) {
			for(int J=j; J<=2*n; J++) {
				if(v[I][J] == 1 && !vis[I][J]) {
					dfs(I, J);
					grpId++;
					ans++;
				}
			}
		}
		
		if(k == n-1) {
			string str = "";
			str += inttobin(ans, 15);
			while(str.length()<100) str+="0";
			return str;
		}
		
		// create string
		vector< pair<int, int> > L; L.clear();
		for(int I=2*n; I>=i; I--) L.push_back({I, j});		
		for(int J=j+1; J<=2*n; J++) L.push_back({i, J});
		
		for(int I=0; I<=grpId; I++) freq[I] = -1;
		
		stack<int> stk;
		string refStr = "";
		
		int Prev = 0;
		int tmpid = 0;
		for(auto c:L) {
			if(Prev == 0 && v[c.first][c.second] == 1) {
				if(freq[newGrpId[c.first][c.second]] == -1) {
					stk.push(tmpid);
					refStr += "1";
					freq[newGrpId[c.first][c.second]] = tmpid;
					ans--;
					tmpid++;
				} else {
					stk.push(tmpid);
					tmpid++;
					refStr += "1";
					while(stk.top() != freq[newGrpId[c.first][c.second]]) {
						stk.pop();
						refStr += "0";
					}
				}
			}
			Prev = v[c.first][c.second];
		}
		
		string str = "";
		str += a[0][0][0];
		str += inttobin(ans, 10);
		str += refStr;
		str += "1";
		while(str.length() < 100) str += "0";
		return str; 
	} else if(i == m || i == m-1) {
		string str = "";
		str += a[0][0][0];
		str += a[2][0][0];
		str += a[2][1][0];
		str += a[2][2][0];
		str += a[2][0].substr(1, k*3);
		while(str.length() < 100) str += "0";
		return str;
	} else if(j == m || j == m-1) {
		string str = "";
		str += a[0][0][0];
		str += a[0][2][0];
		str += a[1][2][0];
		str += a[2][2][0];
		str += a[0][2].substr(1, k*3);
		while(str.length() < 100) str += "0";
		return str;
	}
	return a[0][0][0] + string(99, '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:124:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |    for(int I=0; I<relstr.length(); I++) {
      |                 ~^~~~~~~~~~~~~~~~

• 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