Submission #623830

#	Time	Username	Problem	Language	Result	Execution time	Memory
623830		Lobo	Mars (APIO22_mars)	C++17	29 / 100	127 ms	2836 KiB

mars

#include "mars.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second


std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{

	vector<pair<int,int>> d = {{0,1},{0,-1},{1,0},{-1,0}};
	// cout << " " << i << " " << j << " " << k << " " << n << endl;
	//i,j -> (i/2)*(n+1)+j/2
	string ans(100,'0');
	if(n == 1) {
		int grid[2*n+1][2*n+1];
		for(int i1 = 0; i1 < 2*n+1; i1++) {
			for(int j1 = 0; j1 < 2*n+1; j1++) {
				grid[i1][j1] = a[i1][j1][0]-'0';
				// cout << grid[i1][j1];
			}
		}
		int cnt = 0;
		for(int i1 = 0; i1 < 2*n+1; i1++) {
			for(int j1 = 0; j1 < 2*n+1; j1++) {
				if(grid[i1][j1]) {
					cnt++;
					queue<pair<int,int>> q;
					q.push(mp(i1,j1));
					grid[i1][j1] = 0;
					while(q.size()) {
						int i2 = q.front().fr;
						int j2 = q.front().sc;
						q.pop();
						for(auto x : d) {
							int i3 = i2+x.fr;
							int j3 = j2+x.sc;
							if(i3 < 0 || j3 < 0 || i3 > 2*n || j3 > 2*n || grid[i3][j3] == 0) continue;
							grid[i3][j3] = 0;
							q.push(mp(i3,j3));
						}
					}
				}
			}
		}
		ans = string(100,'0');
		for(int x = 0; x < 25; x++) {
			if((1<<x)&cnt) ans[x] = '1';
		}
		// cout << ans << endl;
	}
	else if(k == 0) {
		for(int i1 = i; i1 <= i+2; i1+=2) {
			for(int j1 = j; j1 <= j+2; j1+=2) {
				ans[(i1/2)*(n+1)+j1/2] = a[i1-i][j1-j][0];
			}
		}
	}
	else {
		for(int i1 = 0; i1 < 100; i1++) {
			ans[i1] = max(ans[i1],a[0][0][i1]);
			ans[i1] = max(ans[i1],a[2][0][i1]);
			ans[i1] = max(ans[i1],a[0][2][i1]);
			ans[i1] = max(ans[i1],a[2][2][i1]);
		}
		if(k == n-1) {
			a[0][0] = ans;
			int grid[2*n+1][2*n+1];
			// cout << " " << a[0][0] << endl;
			// cout << " " << a[0][1] << endl;
			// cout << " " << a[1][0] << endl;
			// cout << " " << a[1][1] << endl;
			for(int i1 = 0; i1 < 2*n+1; i1++) {
				for(int j1 = 0; j1 < 2*n+1; j1++) {
					grid[i1][j1] = a[i1%2][j1%2][(i1/2)*(n+1)+j1/2]-'0';
					if(i1%2 == 0 && j1%2 == 1) {
						grid[i1][j1] = max(grid[i1][j1],a[2][1][(i1/2)*(n+1)+j1/2]-'0');
					}
					if(i1%2 == 1 && j1%2 == 0) {
						grid[i1][j1] = max(grid[i1][j1],a[1][2][(i1/2)*(n+1)+j1/2]-'0');
					}
					// cout << grid[i1][j1];
				}
			}
			int cnt = 0;
			for(int i1 = 0; i1 < 2*n+1; i1++) {
				for(int j1 = 0; j1 < 2*n+1; j1++) {
					if(grid[i1][j1]) {
						// cout << i1 << " " << j1 << endl;
						cnt++;
						queue<pair<int,int>> q;
						q.push(mp(i1,j1));
						grid[i1][j1] = 0;
						while(q.size()) {
							int i2 = q.front().fr;
							int j2 = q.front().sc;
							q.pop();
							// cout << " " << i2 << " " << j2 << endl;
							for(auto x : d) {
								int i3 = i2+x.fr;
								int j3 = j2+x.sc;
								if(i3 < 0 || j3 < 0 || i3 > 2*n || j3 > 2*n || grid[i3][j3] == 0) continue;
								grid[i3][j3] = 0;
								// cout << "   " << i3 << " " << j3 << endl;
								q.push(mp(i3,j3));
							}
						}
					}
				}
			}
			ans = string(100,'0');
			for(int x = 0; x < 25; x++) {
				if((1<<x)&cnt) ans[x] = '1';
			}
			// cout << ans << endl;
		}
	}
	// cout << i << " " << j << " " << k << " " << ans << endl;
	return ans;
}

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