oj.uz

Submission #845676

# Submission time Handle Problem Language Result Execution time Memory
845676 2023-09-06T14:52:20 Z vjudge1 Skandi (COCI20_skandi) C++17
18 / 110
 118 ms 680 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20;
const ll MAXN = 3e5 + 5;

int N, M;
vector<string> grid;
void fillGrid(pair<bool,pair<int,int>> P, vector<string> &new_grid) {
	if (P.f) {
		pair<int,int> now = {P.s.f, P.s.s + 1};
		while (now.s <= M-1 && new_grid[now.f][now.s] == '0') {
			new_grid[now.f][now.s] = '1';
			now.s++;
		}
	} else {
		pair<int,int> now = {P.s.f + 1, P.s.s};
		while (now.f <= N-1 && new_grid[now.f][now.s] == '0') {
			new_grid[now.f][now.s] = '1';
			now.f++;
		}
	}
}

int main() {
	fast
	cin >> N >> M;

	grid = vector<string>(N);
	for (int i = 0; i < N; i++)
		cin >> grid[i];

	vector<pair<bool,pair<int,int>>> ones;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (grid[i][j] == '1')
				ones.push_back({false, {i, j}});
		}
	}

	int n = ones.size();
	for (int i = 0; i < n; i++)
		ones.push_back({true, ones[i].s});

	const int mx_mask = (1<<ones.size())-1;
	int ans = 1e5;
	int ans_mask = -1;
	for (int mask = 0; mask <= mx_mask; mask++) {
		vector<string> new_grid = grid;
		for (int i = 0; i < ones.size(); i++) {
			if ((1<<i) & mask)
				fillGrid(ones[i], new_grid);
		}

		bool control = true;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (new_grid[i][j] == '0')
					control = false;
			}
		}

		if (control && ans > __builtin_popcount(mask)) {
			ans = __builtin_popcount(mask);
			ans_mask = mask;
		}
	}

	cout << ans << "\n";
	for (int i = 0; i < ones.size(); i++) {
		if ((1<<i) & ans_mask) {
			cout << ones[i].s.f + 1 << " " << ones[i].s.s + 1 << " ";
			if (ones[i].f)
				cout << "DESNO\n";
			else
				cout << "DOLJE\n";
		}
	}
}

Compilation message

skandi.cpp: In function 'int main()':
skandi.cpp:55:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<bool, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for (int i = 0; i < ones.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
skandi.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<bool, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for (int i = 0; i < ones.size(); i++) {
      |                  ~~^~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 344 KB Correct.
2 Correct 10 ms 344 KB Correct.
3 Correct 10 ms 344 KB Correct.
4 Correct 10 ms 344 KB Correct.
5 Correct 39 ms 348 KB Correct.
6 Correct 39 ms 432 KB Correct.
7 Correct 45 ms 680 KB Correct.
8 Correct 42 ms 344 KB Correct.
9 Correct 38 ms 344 KB Correct.
10 Correct 50 ms 344 KB Correct.
11 Correct 42 ms 344 KB Correct.
12 Correct 42 ms 348 KB Correct.
13 Correct 38 ms 344 KB Correct.
14 Correct 37 ms 424 KB Correct.
15 Correct 37 ms 344 KB Correct.
16 Correct 10 ms 344 KB Correct.
17 Correct 35 ms 344 KB Correct.
18 Correct 39 ms 344 KB Correct.
19 Correct 2 ms 344 KB Correct.
20 Correct 10 ms 348 KB Correct.
21 Correct 35 ms 348 KB Correct.
22 Correct 10 ms 344 KB Correct.
23 Correct 37 ms 596 KB Correct.

Subtask #2
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 484 KB First line is not correct.
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 344 KB Correct.
2 Correct 10 ms 344 KB Correct.
3 Correct 10 ms 344 KB Correct.
4 Correct 10 ms 344 KB Correct.
5 Correct 39 ms 348 KB Correct.
6 Correct 39 ms 432 KB Correct.
7 Correct 45 ms 680 KB Correct.
8 Correct 42 ms 344 KB Correct.
9 Correct 38 ms 344 KB Correct.
10 Correct 50 ms 344 KB Correct.
11 Correct 42 ms 344 KB Correct.
12 Correct 42 ms 348 KB Correct.
13 Correct 38 ms 344 KB Correct.
14 Correct 37 ms 424 KB Correct.
15 Correct 37 ms 344 KB Correct.
16 Correct 10 ms 344 KB Correct.
17 Correct 35 ms 344 KB Correct.
18 Correct 39 ms 344 KB Correct.
19 Correct 2 ms 344 KB Correct.
20 Correct 10 ms 348 KB Correct.
21 Correct 35 ms 348 KB Correct.
22 Correct 10 ms 344 KB Correct.
23 Correct 37 ms 596 KB Correct.
24 Incorrect 118 ms 484 KB First line is not correct.
25 Halted 0 ms 0 KB -