Submission #108920

#	Time	Username	Problem	Language	Result	Execution time	Memory
108920		Markomafko972	Trapezi (COI17_trapezi)	C++14	100 / 100	88 ms	67064 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];
int g[200][(1 << 20)][2];
 
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");
	
}

pair<int, int> mijenjaj(int msk, int w) {
	if (w == v.size()) return {0, 0};

	int x = v[w].X;
	int y = v[w].Y;
	
	int d = 0;
	for (int i = 1; i < pr.size(); i ++) {
		if (pr[i].X == x+1 && pr[i].Y == y) {
			d = 1;
		}
		else if ((x == pr[i].X && pr[i].Y > y) || x+1 == pr[i].X) {
			msk = msk|(1 << pr[i].Y);
		}
	}
	
	//cout << msk << " i " << d << endl;
	
	if (y == 0) {
		if ((msk&(1 << 0)) > 0) msk -= (1 << 0);
		return {msk, 0};
	}
	else {
		int nm = 0;
		for (int i = 0; i < y; i ++) {
			if ((msk&(1 << i)) > 0) nm = (nm|(1 << i));
		}
		
		if (d == 1) nm = (nm|(1 << y));
		
		//cout << "nm: " << nm << endl;
		
		int i = y+1;
		while (bio[x][i] != -1) {
			//cout << i << ": " << (msk&(1 << i)) << endl;
			if ((msk&(1 << i)) > 0) nm = (nm|(1 << i));
			i ++;
		}
		
		
		return {nm, 0};
	}
}
 
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, int mask, int d) {	
	if (w == v.size()) {
		da = 1;
		return;
	}
	
	if (g[w][mask][d]) return;
	g[w][mask][d] = 1;

	int x = v[w].X;
	int y = v[w].Y;
	
	//cout << x << "," << y << ": " << mask << ", " << d << endl;
	
	if (bio[x][y] > 0 || a[x][y] == 0) {
		if (w+1 == v.size()) dfs(w+1, 0, 0);
		if (v[w+1].Y == 0) {
			int nmask = mask;
			if ((nmask&(1 << 0)) > 0) nmask -= (1 << 0);
			dfs(w+1, nmask, 0);	
		}
		else {
			int nmask = 0;
			for (int i = 0; i <= y; i ++) {
				if ((mask&(1 << i)) > 0) nmask = nmask|(1 << i);
			}
			
			if (d > 0) nmask = nmask|(1 << (y+1));
			
			int i = y+2;
			while (bio[x][i] != -1) {
				if ((mask&(1 << i)) > 0) nmask = nmask|(1 << i);
				i ++;
			}
			
			//cout << nmask << endl;
			dfs(w+1, nmask, 0);
		}
		
		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()) {
			pair<int, int> nova = mijenjaj(mask, w+1);
			dfs(w+1, nova.X, nova.Y);
			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()) {
				pair<int, int> nova = mijenjaj(mask, w+1);
				dfs(w+1, nova.X, nova.Y);
				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()) {
				pair<int, int> nova = mijenjaj(mask, w+1);
				dfs(w+1, nova.X, nova.Y);
				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()) {
				pair<int, int> nova = mijenjaj(mask, w+1);
				dfs(w+1, nova.X, nova.Y);
				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()) {
				pair<int, int> nova = mijenjaj(mask, w+1);
				dfs(w+1, nova.X, nova.Y);
				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, 0, 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 'std::pair<int, int> mijenjaj(int, int)':
trapezi.cpp:36:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (w == v.size()) return {0, 0};
      ~~^~~~~~~~~~~
trapezi.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < pr.size(); i ++) {
                  ~~^~~~~~~~~~~
trapezi.cpp: In function 'int provjeri()':
trapezi.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < pr.size(); i ++) {
                  ~~^~~~~~~~~~~
trapezi.cpp:98: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, int, int)':
trapezi.cpp:112:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (w == v.size()) {
      ~~^~~~~~~~~~~
trapezi.cpp:126:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (w+1 == v.size()) dfs(w+1, 0, 0);
       ~~~~^~~~~~~~~~~
trapezi.cpp: In function 'void ispisi()':
trapezi.cpp:31: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: 37 / 37