oj.uz

Submission #390608

# Submission time Handle Problem Language Result Execution time Memory
390608 2021-04-16T11:37:09 Z SuhaibSawalha1 Vision Program (IOI19_vision) C++17
14 / 100
 57 ms 8812 KB 
#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
 
int dist (array<int, 2> a, array<int, 2> b) {
	return abs(a[0] - b[0]) + abs(a[1] - b[1]);
}
 
void construct_network(int n, int m, int k) {
	auto val = [&] (int i, int j) {
		return i * m + j;
	};
	vector<int> OR;
	int cur = n * m - 1;
	if (k == 1) {
		int row[n], col[m];
		int xor_for_rows, xor_for_cols;
		vector<int> ask_r, ask_c;
		for (int i = 0; i < n; ++i) {
			vector<int> p;
			for (int j = 0; j < m; ++j) {
				p.push_back(val(i, j));
			}
			add_or(p);
			row[i] = ++cur;
			ask_r.push_back(cur);
		}
		for (int j = 0; j < m; ++j) {
			vector<int> p;
			for (int i = 0; i < n; ++i) {
				p.push_back(val(i, j));
			}
			add_or(p);
			col[j] = ++cur;
			ask_c.push_back(cur);
		}
		add_xor(ask_r);
		xor_for_rows = ++cur;
		add_xor(ask_c);
		xor_for_cols = ++cur;
		for (int i = 1; i < n; ++i) {
			add_and({row[i - 1], row[i], xor_for_cols});
			OR.push_back(++cur);
		}
		for (int i = 1; i < m; ++i) {
			add_and({col[i - 1], col[i], xor_for_rows});
			OR.push_back(++cur);
		}
	}
	else {
		int q = 1e4 - 1;
		vector<int> ask[n * m];
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				for (int h = 0; h < n; ++h) {
					for (int w = 0; w < m; ++w) {
						if (dist({i, j}, {h, w}) == k) {
							ask[val(i, j)].push_back(val(h, w));
						}
					}
				}
			}
		}
		set<int> asked[n * m];
		sort(ask, ask + n * m, [](auto &a, auto &b) {
			return a.size() > b.size();
		});
		for (int i = 0; i < n * m; ++i) {
			vector<int> to_ask;
			for (int j : ask[i]) {
				if (!asked[j].count(i)) {
					asked[i].insert(j);
					to_ask.push_back(j);
				}
			}
			if (to_ask.size() && q > 1) {
				add_xor(to_ask), ++cur;
				add_and({i, cur}); ++cur;
				q -= 2;
				OR.push_back(cur);
			}
		}
	}
	add_or(OR);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB on inputs (0, 0), (0, 1), expected 0, but computed 1
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB on inputs (0, 0), (0, 1), expected 0, but computed 1
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB on inputs (0, 0), (0, 1), expected 0, but computed 1
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB on inputs (0, 0), (0, 1), expected 0, but computed 1
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB on inputs (0, 0), (0, 1), expected 0, but computed 1
3 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 57 ms 8812 KB on inputs (0, 0), (29, 1), expected 0, but computed 1
5 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1032 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 13 ms 1100 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB on inputs (0, 0), (0, 1), expected 0, but computed 1
3 Halted 0 ms 0 KB -