Submission #845676

#	Time	Username	Problem	Language	Result	Execution time	Memory
845676		vjudge1	Skandi (COCI20_skandi)	C++17	18 / 110	118 ms	680 KiB

Main

#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 (stderr)

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 / 18
• Subtask 2: 0 / 32
• Subtask 3: 0 / 60