oj.uz

Submission #623831

# Submission time Handle Problem Language Result Execution time Memory
623831 2022-08-06T15:22:11 Z Lobo Mars (APIO22_mars) C++17
0 / 100
 1 ms 200 KB 
#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+n%2)+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+n%2)+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+n%2)+j1/2]-'0';
					if(i1%2 == 0 && j1%2 == 1) {
						grid[i1][j1] = max(grid[i1][j1],a[2][1][(i1/2)*(n+n%2)+j1/2]-'0');
					}
					if(i1%2 == 1 && j1%2 == 0) {
						grid[i1][j1] = max(grid[i1][j1],a[1][2][(i1/2)*(n+n%2)+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
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -