oj.uz

Submission #584582

# Submission time Handle Problem Language Result Execution time Memory
584582 2022-06-27T14:58:34 Z rainboy Mars (APIO22_mars) C++17
14 / 100
 18 ms 2360 KB 
#include "mars.h"
#include <string.h>

using namespace std;

typedef vector<string> vs;
typedef vector<vs> vvs;

const int N = 20, N_ = N * 2 + 1;

int find(int *ds, int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds, ds[i]));
}

void join(int *ds, int i, int j) {
	i = find(ds, i);
	j = find(ds, j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

string process(vvs ss, int i, int j, int k, int n) {
	string s(100, '0');
	int n_ = (k + 1) * 2 + 1;
	if (n == 1) {
		int ds[N_ * N_];
		memset(ds, -1, n_ * n_ * sizeof *ds);
		for (i = 0; i < n_; i++)
			for (j = 0; j < n_; j++)
				if (ss[i][j][0] == '1') {
					if (i > 0 && ss[i - 1][j][0] == '1')
						join(ds, i * n_ + j, (i - 1) * n_ + j);
					if (j > 0 && ss[i][j - 1][0] == '1')
						join(ds, i * n_ + j, i * n_ + (j - 1));
				}
		int c = 0;
		for (i = 0; i < n_ * n_; i++)
			if (ds[i] < 0 && ss[i / n_][i % n_][0] == '1')
				c++;
		string t(100, '0');
		for (int h = 0; h < 10; h++)
			t[h] = (c >> h & 1) + '0';
		return t;
	} else {
		int m = (n + 1) / 2;
		if (k < m) {
			for (int i1 = 0; i1 < 3; i1++)
				for (int j1 = 0; j1 < 3; j1++)
					for (int i2 = 0; i2 < n_ - 2; i2++)
						for (int j2 = 0; j2 < n_ - 2; j2++)
							s[(i1 + i2) * n_ + (j1 + j2)] = ss[i1][j1][i2 * (n_ - 2) + j2];
			return s;
		} else if (k < n - 1) {
			if (i == (n - 1 - k) * 2 && j == 0)
				return ss[2][0];
			else if (i == 0 && j == (n - 1 - k) * 2)
				return ss[0][2];
			if (i == (n - 1 - k) * 2 && j == (n - 1 - k) * 2)
				return ss[2][2];
			return ss[0][0];
		} else {
			int m_ = m * 2 + 1;
			for (int i1 = 0; i1 < 3; i1 += 2)
				for (int j1 = 0; j1 < 3; j1 += 2)
					for (int i2 = 0; i2 < m_; i2++)
						for (int j2 = 0; j2 < m_; j2++)
							s[(i1 * (n - m) + i2) * n_ + (j1 * (n - m) + j2)] = ss[i1][j1][i2 * m_ + j2];
			int ds[N_ * N_];
			memset(ds, -1, n_ * n_ * sizeof *ds);
			for (i = 0; i < n_; i++)
				for (j = 0; j < n_; j++)
					if (s[i * n_ + j] == '1') {
						if (i > 0 && s[(i - 1) * n_ + j] == '1')
							join(ds, i * n_ + j, (i - 1) * n_ + j);
						if (j > 0 && s[i * n_ + (j - 1)] == '1')
							join(ds, i * n_ + j, i * n_ + (j - 1));
					}
			int c = 0;
			for (i = 0; i < n_ * n_; i++)
				if (ds[i] < 0 && s[i] == '1')
					c++;
			string t(100, '0');
			for (int h = 0; h < 10; h++)
				t[h] = (c >> h & 1) + '0';
			return t;
		}
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1776 KB Output is correct
2 Correct 8 ms 1880 KB Output is correct
3 Correct 8 ms 1960 KB Output is correct
4 Correct 8 ms 1956 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1776 KB Output is correct
2 Correct 8 ms 1880 KB Output is correct
3 Correct 8 ms 1960 KB Output is correct
4 Correct 8 ms 1956 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 10 ms 1952 KB Output is correct
8 Correct 18 ms 2020 KB Output is correct
9 Correct 16 ms 2212 KB Output is correct
10 Correct 16 ms 2360 KB Output is correct
11 Correct 17 ms 2216 KB Output is correct
12 Correct 16 ms 2228 KB Output is correct
13 Correct 16 ms 1956 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1776 KB Output is correct
2 Correct 8 ms 1880 KB Output is correct
3 Correct 8 ms 1960 KB Output is correct
4 Correct 8 ms 1956 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 10 ms 1952 KB Output is correct
8 Correct 18 ms 2020 KB Output is correct
9 Correct 16 ms 2212 KB Output is correct
10 Correct 16 ms 2360 KB Output is correct
11 Correct 17 ms 2216 KB Output is correct
12 Correct 16 ms 2228 KB Output is correct
13 Correct 16 ms 1956 KB Output is correct
14 Runtime error 4 ms 432 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 8 ms 1776 KB Output is correct
2 Correct 8 ms 1880 KB Output is correct
3 Correct 8 ms 1960 KB Output is correct
4 Correct 8 ms 1956 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 10 ms 1952 KB Output is correct
8 Correct 18 ms 2020 KB Output is correct
9 Correct 16 ms 2212 KB Output is correct
10 Correct 16 ms 2360 KB Output is correct
11 Correct 17 ms 2216 KB Output is correct
12 Correct 16 ms 2228 KB Output is correct
13 Correct 16 ms 1956 KB Output is correct
14 Runtime error 4 ms 432 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 8 ms 1776 KB Output is correct
2 Correct 8 ms 1880 KB Output is correct
3 Correct 8 ms 1960 KB Output is correct
4 Correct 8 ms 1956 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 10 ms 1952 KB Output is correct
8 Correct 18 ms 2020 KB Output is correct
9 Correct 16 ms 2212 KB Output is correct
10 Correct 16 ms 2360 KB Output is correct
11 Correct 17 ms 2216 KB Output is correct
12 Correct 16 ms 2228 KB Output is correct
13 Correct 16 ms 1956 KB Output is correct
14 Runtime error 4 ms 432 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 8 ms 1776 KB Output is correct
2 Correct 8 ms 1880 KB Output is correct
3 Correct 8 ms 1960 KB Output is correct
4 Correct 8 ms 1956 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 10 ms 1952 KB Output is correct
8 Correct 18 ms 2020 KB Output is correct
9 Correct 16 ms 2212 KB Output is correct
10 Correct 16 ms 2360 KB Output is correct
11 Correct 17 ms 2216 KB Output is correct
12 Correct 16 ms 2228 KB Output is correct
13 Correct 16 ms 1956 KB Output is correct
14 Runtime error 4 ms 432 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 8 ms 1776 KB Output is correct
2 Correct 8 ms 1880 KB Output is correct
3 Correct 8 ms 1960 KB Output is correct
4 Correct 8 ms 1956 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 10 ms 1952 KB Output is correct
8 Correct 18 ms 2020 KB Output is correct
9 Correct 16 ms 2212 KB Output is correct
10 Correct 16 ms 2360 KB Output is correct
11 Correct 17 ms 2216 KB Output is correct
12 Correct 16 ms 2228 KB Output is correct
13 Correct 16 ms 1956 KB Output is correct
14 Runtime error 4 ms 432 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 8 ms 1776 KB Output is correct
2 Correct 8 ms 1880 KB Output is correct
3 Correct 8 ms 1960 KB Output is correct
4 Correct 8 ms 1956 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 10 ms 1952 KB Output is correct
8 Correct 18 ms 2020 KB Output is correct
9 Correct 16 ms 2212 KB Output is correct
10 Correct 16 ms 2360 KB Output is correct
11 Correct 17 ms 2216 KB Output is correct
12 Correct 16 ms 2228 KB Output is correct
13 Correct 16 ms 1956 KB Output is correct
14 Runtime error 4 ms 432 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 8 ms 1776 KB Output is correct
2 Correct 8 ms 1880 KB Output is correct
3 Correct 8 ms 1960 KB Output is correct
4 Correct 8 ms 1956 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 10 ms 1952 KB Output is correct
8 Correct 18 ms 2020 KB Output is correct
9 Correct 16 ms 2212 KB Output is correct
10 Correct 16 ms 2360 KB Output is correct
11 Correct 17 ms 2216 KB Output is correct
12 Correct 16 ms 2228 KB Output is correct
13 Correct 16 ms 1956 KB Output is correct
14 Runtime error 4 ms 432 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 8 ms 1776 KB Output is correct
2 Correct 8 ms 1880 KB Output is correct
3 Correct 8 ms 1960 KB Output is correct
4 Correct 8 ms 1956 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 10 ms 1952 KB Output is correct
8 Correct 18 ms 2020 KB Output is correct
9 Correct 16 ms 2212 KB Output is correct
10 Correct 16 ms 2360 KB Output is correct
11 Correct 17 ms 2216 KB Output is correct
12 Correct 16 ms 2228 KB Output is correct
13 Correct 16 ms 1956 KB Output is correct
14 Runtime error 4 ms 432 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -