oj.uz

Submission #984021

# Submission time Handle Problem Language Result Execution time Memory
984021 2024-05-16T09:13:42 Z vjudge1 Mars (APIO22_mars) C++17
14 / 100
 16 ms 4652 KB 
#include <bits/stdc++.h>
#include "mars.h"

using namespace std;

const int N = 100;

bool a[N][N];

void clear() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			a[i][j] = false;
}

void colour(int i, int j, int k, string s) {
	for (int x = 0; x < 100; x++) {
		a[i + x / (2 * k + 1)][j + x % (2 * k + 1)] |= (s[x] == '1');
	}
}

string decode(int i, int j, int k) {
	string s;
	for (int x = 0; x <= 2 * k; x++) {
		for (int y = 0; y <= 2 * k; y++) {
			s += a[i + x][j + y] ? '1' : '0';
		}
	}
	while ((int)s.size() < 100) s += '0';
	assert((int)s.size() == 100);
	return s;
}

int bfs() {
	vector<pair<int, int>> dirs = {{-1, 0}, {+1, 0}, {0, -1}, {0, +1}};
	auto move = [&](pair<int, int> s, int i) -> pair<int, int> {
		assert(0 <= i && i < 4);
		return {s.first + dirs[i].first, s.second + dirs[i].second};
	};
	auto check = [&](pair<int, int> b) -> bool {
		return (0 <= b.first && b.first < N && 0 <= b.second && b.second < N && a[b.first][b.second]);
	};

	bool us[N][N] = {};

	int cnt = 0;
	queue<pair<int, int>> q;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (us[i][j] || !a[i][j]) continue;
			cnt++;
			us[i][j] = true;
			q.push({i, j});
			while (!q.empty()) {
				pair<int, int> s = q.front();
				q.pop();
				for (auto d = 0; d < 4; d++) {
					auto next = move(s, d);
					if (check(next) && !us[next.first][next.second]) {
						us[next.first][next.second] = true;
						q.push(next);
					}
				}
			}
		}
	}
	return cnt;
}

string process(vector <vector<string>> a, int i, int j, int k, int n) {
	clear();
	for (int r1 = 0; r1 < 3; r1++) {
		for (int c1 = 0; c1 < 3; c1++) {
			colour(i + r1, j + c1, k, a[r1][c1]);
		}
	}
	if (k != n - 1) 
		return decode(i, j, k + 1);
	int ans = bfs();
	string res(100, '0');
	for (int i = 0; i < 30; i++) {
		res[i] = ((ans >> i & 1) ? '1' : '0');
	}
	return res;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3592 KB Output is correct
2 Correct 6 ms 4492 KB Output is correct
3 Correct 5 ms 3948 KB Output is correct
4 Correct 6 ms 4508 KB Output is correct
5 Correct 5 ms 4320 KB Output is correct
6 Correct 8 ms 4012 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3592 KB Output is correct
2 Correct 6 ms 4492 KB Output is correct
3 Correct 5 ms 3948 KB Output is correct
4 Correct 6 ms 4508 KB Output is correct
5 Correct 5 ms 4320 KB Output is correct
6 Correct 8 ms 4012 KB Output is correct
7 Correct 8 ms 4652 KB Output is correct
8 Correct 15 ms 4068 KB Output is correct
9 Correct 16 ms 4396 KB Output is correct
10 Correct 15 ms 4048 KB Output is correct
11 Correct 16 ms 4556 KB Output is correct
12 Correct 14 ms 3672 KB Output is correct
13 Correct 14 ms 4160 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3592 KB Output is correct
2 Correct 6 ms 4492 KB Output is correct
3 Correct 5 ms 3948 KB Output is correct
4 Correct 6 ms 4508 KB Output is correct
5 Correct 5 ms 4320 KB Output is correct
6 Correct 8 ms 4012 KB Output is correct
7 Correct 8 ms 4652 KB Output is correct
8 Correct 15 ms 4068 KB Output is correct
9 Correct 16 ms 4396 KB Output is correct
10 Correct 15 ms 4048 KB Output is correct
11 Correct 16 ms 4556 KB Output is correct
12 Correct 14 ms 3672 KB Output is correct
13 Correct 14 ms 4160 KB Output is correct
14 Runtime error 3 ms 464 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3592 KB Output is correct
2 Correct 6 ms 4492 KB Output is correct
3 Correct 5 ms 3948 KB Output is correct
4 Correct 6 ms 4508 KB Output is correct
5 Correct 5 ms 4320 KB Output is correct
6 Correct 8 ms 4012 KB Output is correct
7 Correct 8 ms 4652 KB Output is correct
8 Correct 15 ms 4068 KB Output is correct
9 Correct 16 ms 4396 KB Output is correct
10 Correct 15 ms 4048 KB Output is correct
11 Correct 16 ms 4556 KB Output is correct
12 Correct 14 ms 3672 KB Output is correct
13 Correct 14 ms 4160 KB Output is correct
14 Runtime error 3 ms 464 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3592 KB Output is correct
2 Correct 6 ms 4492 KB Output is correct
3 Correct 5 ms 3948 KB Output is correct
4 Correct 6 ms 4508 KB Output is correct
5 Correct 5 ms 4320 KB Output is correct
6 Correct 8 ms 4012 KB Output is correct
7 Correct 8 ms 4652 KB Output is correct
8 Correct 15 ms 4068 KB Output is correct
9 Correct 16 ms 4396 KB Output is correct
10 Correct 15 ms 4048 KB Output is correct
11 Correct 16 ms 4556 KB Output is correct
12 Correct 14 ms 3672 KB Output is correct
13 Correct 14 ms 4160 KB Output is correct
14 Runtime error 3 ms 464 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3592 KB Output is correct
2 Correct 6 ms 4492 KB Output is correct
3 Correct 5 ms 3948 KB Output is correct
4 Correct 6 ms 4508 KB Output is correct
5 Correct 5 ms 4320 KB Output is correct
6 Correct 8 ms 4012 KB Output is correct
7 Correct 8 ms 4652 KB Output is correct
8 Correct 15 ms 4068 KB Output is correct
9 Correct 16 ms 4396 KB Output is correct
10 Correct 15 ms 4048 KB Output is correct
11 Correct 16 ms 4556 KB Output is correct
12 Correct 14 ms 3672 KB Output is correct
13 Correct 14 ms 4160 KB Output is correct
14 Runtime error 3 ms 464 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3592 KB Output is correct
2 Correct 6 ms 4492 KB Output is correct
3 Correct 5 ms 3948 KB Output is correct
4 Correct 6 ms 4508 KB Output is correct
5 Correct 5 ms 4320 KB Output is correct
6 Correct 8 ms 4012 KB Output is correct
7 Correct 8 ms 4652 KB Output is correct
8 Correct 15 ms 4068 KB Output is correct
9 Correct 16 ms 4396 KB Output is correct
10 Correct 15 ms 4048 KB Output is correct
11 Correct 16 ms 4556 KB Output is correct
12 Correct 14 ms 3672 KB Output is correct
13 Correct 14 ms 4160 KB Output is correct
14 Runtime error 3 ms 464 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3592 KB Output is correct
2 Correct 6 ms 4492 KB Output is correct
3 Correct 5 ms 3948 KB Output is correct
4 Correct 6 ms 4508 KB Output is correct
5 Correct 5 ms 4320 KB Output is correct
6 Correct 8 ms 4012 KB Output is correct
7 Correct 8 ms 4652 KB Output is correct
8 Correct 15 ms 4068 KB Output is correct
9 Correct 16 ms 4396 KB Output is correct
10 Correct 15 ms 4048 KB Output is correct
11 Correct 16 ms 4556 KB Output is correct
12 Correct 14 ms 3672 KB Output is correct
13 Correct 14 ms 4160 KB Output is correct
14 Runtime error 3 ms 464 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3592 KB Output is correct
2 Correct 6 ms 4492 KB Output is correct
3 Correct 5 ms 3948 KB Output is correct
4 Correct 6 ms 4508 KB Output is correct
5 Correct 5 ms 4320 KB Output is correct
6 Correct 8 ms 4012 KB Output is correct
7 Correct 8 ms 4652 KB Output is correct
8 Correct 15 ms 4068 KB Output is correct
9 Correct 16 ms 4396 KB Output is correct
10 Correct 15 ms 4048 KB Output is correct
11 Correct 16 ms 4556 KB Output is correct
12 Correct 14 ms 3672 KB Output is correct
13 Correct 14 ms 4160 KB Output is correct
14 Runtime error 3 ms 464 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3592 KB Output is correct
2 Correct 6 ms 4492 KB Output is correct
3 Correct 5 ms 3948 KB Output is correct
4 Correct 6 ms 4508 KB Output is correct
5 Correct 5 ms 4320 KB Output is correct
6 Correct 8 ms 4012 KB Output is correct
7 Correct 8 ms 4652 KB Output is correct
8 Correct 15 ms 4068 KB Output is correct
9 Correct 16 ms 4396 KB Output is correct
10 Correct 15 ms 4048 KB Output is correct
11 Correct 16 ms 4556 KB Output is correct
12 Correct 14 ms 3672 KB Output is correct
13 Correct 14 ms 4160 KB Output is correct
14 Runtime error 3 ms 464 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -