oj.uz

Submission #108092

# Submission time Handle Problem Language Result Execution time Memory
108092 2019-04-27T09:36:08 Z Markomafko972 Trapezi (COI17_trapezi) C++14
63 / 100
 500 ms 432 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 10 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 432 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Execution timed out 1038 ms 384 KB Time limit exceeded
6 Halted 0 ms 0 KB -