Submission #108092

#	Time	Username	Problem	Language	Result	Execution time	Memory
108092		Markomafko972	Trapezi (COI17_trapezi)	C++14	63 / 100	1038 ms	432 KiB

trapezi

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int n, m;
char ch;
int a[25][25];
int p[25][25];
vector< pair<int, int> > v;
int maxkr;
int bio[25][25];
int da = 0;
vector< pair<int, int> > pr;
int niz[10];

void ispisi() {
	
	for (int i = 0; i < m; i ++) {
		for (int j = 0; j < maxkr; j ++) {
			if (bio[i][j] != -1) {
				if (bio[i][j] == 0) cout << '.';
				else cout << bio[i][j];
			}
		}
		cout << endl;
	}
	
	cout << endl;
	system("pause");
	
}

int provjeri() {
	for (int i = 0; i <= 6; i ++) niz[i] = 0;
	
	for (int i = 0; i < pr.size(); i ++) {
		int x = pr[i].X;
		int y = pr[i].Y;
		
		niz[bio[x][y+1]] ++;
		if (y-1 >= 0) niz[bio[x][y-1]] ++;
		if (p[x][y] == 0) {
			niz[bio[x+1][y]] ++;
		}
		else if (x-1 >= 0) {
			niz[bio[x-1][y]] ++;
		}
	}
	
	for (int i = 1; i <= 6; i ++) {
		if (niz[i] == 0) {
			for (int j = 0; j < pr.size(); j ++) {
				int x = pr[j].X;
				int y = pr[j].Y;
				bio[x][y] = i;
			}
			
			//ispisi();
			return 1;
		}
	}
	return 0;
}

void dfs(int w) {
	if (w == v.size()) {
		da = 1;
		return;
	}
	
	int x = v[w].X;
	int y = v[w].Y;
	if (bio[x][y] > 0 || a[x][y] == 0) {
		dfs(w+1);
		return;
	}
	
	if (a[x][y+1] == 1 && a[x][y+2] == 1 && bio[x][y+1] == 0 && bio[x][y+2] == 0) {
		pr.clear();
		pr.push_back({x, y});
		pr.push_back({x, y+1});
		pr.push_back({x, y+2});
		if (provjeri()) {
			dfs(w+1);
			if (da) return;
			bio[x][y] = 0;
			bio[x][y+1] = 0;
			bio[x][y+2] = 0;
		}
	}
	
	if (p[x][y] == 0) {
		if (a[x+1][y] == 1 && a[x+1][y-1] == 1 && bio[x+1][y] == 0 && bio[x+1][y-1] == 0) {
			pr.clear();
			pr.push_back({x, y});
			pr.push_back({x+1, y});
			pr.push_back({x+1, y-1});
			if (provjeri()) {
				dfs(w+1);
				if (da) return;
				bio[x][y] = 0;
				bio[x+1][y] = 0;
				bio[x+1][y-1] = 0;
			}
		}
		
		if (a[x+1][y] == 1 && a[x+1][y+1] == 1 && bio[x+1][y] == 0 && bio[x+1][y+1] == 0) {
			pr.clear();
			pr.push_back({x, y});
			pr.push_back({x+1, y});
			pr.push_back({x+1, y+1});
			if (provjeri()) {
				dfs(w+1);
				if (da) return;
				bio[x][y] = 0;
				bio[x+1][y] = 0;
				bio[x+1][y+1] = 0;
			}
		}
		
		if (a[x][y+1] == 1 && a[x+1][y] == 1 && bio[x][y+1] == 0 && bio[x+1][y] == 0) {
			pr.clear();
			pr.push_back({x, y});
			pr.push_back({x, y+1});
			pr.push_back({x+1, y});
			if (provjeri()) {
				dfs(w+1);
				if (da) return;
				bio[x][y] = 0;
				bio[x][y+1] = 0;
				bio[x+1][y] = 0;
			}
		}
	}
	else {
		if (a[x][y+1] == 1 && a[x+1][y+1] == 1 && bio[x][y+1] == 0 && bio[x+1][y+1] == 0) {
			pr.clear();
			pr.push_back({x, y});
			pr.push_back({x, y+1});
			pr.push_back({x+1, y+1});
			if (provjeri()) {
				dfs(w+1);
				if (da) return;
				bio[x][y] = 0;
				bio[x][y+1] = 0;
				bio[x+1][y+1] = 0;
			}
		}
	}
}

int main () {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	m = n*2;
	int poc = n-1;
	int kraj = 3*n;
	maxkr = 3*n;
	memset(bio, -1, sizeof bio);
	for (int i = 0; i < m; i ++) {
		for (int j = poc; j < kraj; j ++) {
			p[i][j] = (i+j+1+n) % 2;
			bio[i][j] = 0;
			v.push_back({i, j});
			cin >> ch;
			if (ch == '0') a[i][j] = 1;
		}
		
		maxkr = max(maxkr, kraj);
		if (i < n-1) {
			poc --;
			kraj ++;
		}
		else if (i >= n) {
			poc ++;
			kraj --;
		}
	}
	
	/*for (int i = 0; i < m; i ++) {
		for (int j = 0; j < maxkr; j ++) {
			cout << p[i][j] << " ";
		}
		cout << endl;
	}*/
	
	dfs(0);
	
	if (da == 0) cout << "nemoguce";
	else {
		for (int i = 0; i < m; i ++) {
			for (int j = 0; j < maxkr; j ++) {
				if (bio[i][j] != -1) {
					if (bio[i][j] == 0) cout << '.';
					else cout << bio[i][j];
				}
			}
			cout << endl;
		}
	}
	
	return 0;
}

Compilation message (stderr)

trapezi.cpp: In function 'int provjeri()':
trapezi.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < pr.size(); i ++) {
                  ~~^~~~~~~~~~~
trapezi.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < pr.size(); j ++) {
                    ~~^~~~~~~~~~~
trapezi.cpp: In function 'void dfs(int)':
trapezi.cpp:67:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (w == v.size()) {
      ~~^~~~~~~~~~~
trapezi.cpp: In function 'void ispisi()':
trapezi.cpp:30:8: warning: ignoring return value of 'int system(const char*)', declared with attribute warn_unused_result [-Wunused-result]
  system("pause");
  ~~~~~~^~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 22 / 22
• Subtask 5: 0 / 37