oj.uz

답안 #785424

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
785424 2023-07-17T09:04:23 Z 박상훈(#10022) Trapezi (COI17_trapezi) C++17
41 / 100
 500 ms 576 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
char bufs[101];
int a[101][101], ans[101][101], cntC;
int buf[101], up[101][101], L[101], R[101], n;
vector<pair<int, int>> adj[101][101];

int ok(int x, int y){
	if (x<1 || x>n*2) return 0;
	if (y<L[x] || y>R[x]) return 0;
	return 1;
}

void init(int n){
	for (int i=1;i<=n;i++){
		L[i] = n+1-i;
		R[i] = L[i] + (n-1+i) * 2;

		for (int j=L[i];j<=R[i];j+=2) up[i][j] = 1;
	}	

	for (int i=n+1;i<=n*2;i++){
		L[i] = L[n*2+1-i];
		R[i] = R[n*2+1-i];

		for (int j=L[i]+1;j<=R[i];j+=2) up[i][j] = 1;
	}

	for (int i=1;i<=n*2;i++){
		for (int j=L[i];j<=R[i];j++){
			if (up[i][j]){
				// printf(" up %d %d\n", i, j);
				if (ok(i, j-1)) adj[i][j].emplace_back(i, j-1);
				if (ok(i, j+1)) adj[i][j].emplace_back(i, j+1);
				if (ok(i+1, j)) adj[i][j].emplace_back(i+1, j);
			}

			else{
				if (ok(i-1, j)) adj[i][j].emplace_back(i-1, j);
				if (ok(i, j-1)) adj[i][j].emplace_back(i, j-1);
				if (ok(i, j+1)) adj[i][j].emplace_back(i, j+1);
			}
		}
	}
}

void input(int n){
	for (int i=1;i<=n*2;i++){
		scanf("%s", bufs);
		for (int j=0;j<=R[i]-L[i];j++) a[i][j+L[i]] = bufs[j];
	}
}

void output(int n){
	for (int i=1;i<=n*2;i++){
		for (int j=L[i];j<=R[i];j++){
			if (ans[i][j]) printf("%c", '0' + ans[i][j]);
			else printf("%c", (char)a[i][j]);
		} 
		printf("\n");
	}

	exit(0);
}

void color(int n){
	for (int z=1;z<=cntC;z++){
		fill(buf+1, buf+7, 0);
		
		for (int i=1;i<=n*2;i++){
			for (int j=L[i];j<=R[i];j++) if (a[i][j]==z + '0'){
				for (auto &[x, y]:adj[i][j]) if (ans[x][y]!=0) buf[ans[x][y]] = 1;
			}
		}

		int col = -1;
		for (int i=1;i<=6;i++) if (!buf[i]) col = i;
		assert(col!=-1);

		for (int i=1;i<=n*2;i++){
			for (int j=L[i];j<=R[i];j++) if (a[i][j]==z + '0'){
				ans[i][j] = col;
			}
		}
	}
}

void dfs();
inline int push(int x1, int y1, int x2, int y2, int x3, int y3, bool flag){
	if (x2 < 1 || x2 > n*2) return 0;
	if (x3 < 1 || x3 > n*2) return 0;
	if (y2 < L[x2] || y2 > R[x2]) return 0;
	if (y3 < L[x3] || y3 > R[x3]) return 0;

	if (a[x2][y2]!='0' || a[x3][y3]!='0') return 0;

	// fill(buf+1, buf+7, 0);
	// for (auto &[x, y]:adj[x1][y1]) if (a[x][y]!='0' && a[x][y]!='.') buf[a[x][y]-'0'] = 1;
	// for (auto &[x, y]:adj[x2][y2]) if (a[x][y]!='0' && a[x][y]!='.') buf[a[x][y]-'0'] = 1;
	// for (auto &[x, y]:adj[x3][y3]) if (a[x][y]!='0' && a[x][y]!='.') buf[a[x][y]-'0'] = 1;

	// int col = -1;
	// for (int i=1;i<=6;i++) if (!buf[i]) {col = i; break;}
	// if (col==-1) return;

	if (flag){
		a[x1][y1] = a[x2][y2] = a[x3][y3] = (++cntC) + '0';
		dfs();
		--cntC;
		a[x1][y1] = a[x2][y2] = a[x3][y3] = '0';
	}

	return 1;
}

int count(int x, int y, bool flag = false){
	int ret = 0;
	if (up[x][y]){
		ret += push(x, y, x, y-2, x, y-1, flag);
		ret += push(x, y, x, y-1, x, y+1, flag);
		ret += push(x, y, x, y+1, x, y+2, flag);
		
		ret += push(x, y, x-1, y+1, x, y+1, flag);
		ret += push(x, y, x, y+1, x+1, y, flag);
		ret += push(x, y, x+1, y, x+1, y-1, flag);

		ret += push(x, y, x-1, y-1, x, y-1, flag);
		ret += push(x, y, x, y-1, x+1, y, flag);
		ret += push(x, y, x+1, y, x+1, y+1, flag);
	}

	else{
		ret += push(x, y, x, y-2, x, y-1, flag);
		ret += push(x, y, x, y-1, x, y+1, flag);
		ret += push(x, y, x, y+1, x, y+2, flag);

		ret += push(x, y, x-1, y+1, x-1, y, flag);
		ret += push(x, y, x-1, y, x, y-1, flag);
		ret += push(x, y, x, y-1, x+1, y-1, flag);

		ret += push(x, y, x-1, y-1, x-1, y, flag);
		ret += push(x, y, x-1, y, x, y+1, flag);
		ret += push(x, y, x, y+1, x+1, y+1, flag);
	}

	return ret;
}

// int fail;
void dfs(){
	// if (fail > 100000){
	// 	printf("nemoguce\n");
	// 	exit(0);
	// }
	int mn = 69, ii = -1, jj = -1;
	vector<pair<int, int>> C;

	for (int z=n;z>=1;z--){
		for (int i=n+1-z;i<=n+z;i++){
			int s = R[i]-3, e = R[i];
			if (i==n+1-z || i==n+z) s = L[i], e = R[i];

			for (int j=s;j<=e;j++) if (a[i][j]=='0'){
				int tmp = count(i, j);
				if (tmp < mn){
					mn = tmp;
					// ii = i, jj = j;
					C.clear();
					C.emplace_back(i, j);
				}

				else if (tmp==mn) C.emplace_back(i, j);
			}
		}

		if (mn==0) return;
		if (mn!=69){
			random_shuffle(C.begin(), C.end());
			ii = C[0].first, jj = C[0].second;
			count(ii, jj, 1);
			return;
		}
	}
	

	// if (mn==69){
	// 	for (int i=1;i<=n*2;i++){
	// 		for (int j=L[i];j<=R[i];j++) if (a[i][j]=='0'){
	// 			int tmp = count(i, j);
	// 			if (tmp < mn){
	// 				mn = tmp;
	// 				// ii = i, jj = j;
	// 				C.clear();
	// 				C.emplace_back(i, j);
	// 			}

	// 			else if (tmp==mn) C.emplace_back(i, j);
	// 		}
	// 	}
	// }
	

	// printf("ok mn = %d / %d %d\n", mn, ii, jj);
	if (mn==69){
		color(n);
		output(n);
	}

	if (mn==0){
		// fail++;
		return;
	} 

	random_shuffle(C.begin(), C.end());
	ii = C[0].first, jj = C[0].second;
	count(ii, jj, 1);

	// if (y > R[x]) {dfs(x+1, L[x+1]); return;}
	// if (x==n*2 && y==R[x]){
	// 	if (a[x][y]!='0'){
	// 		color(n);
	// 		output(n);
	// 	}
	// 	return;
	// }

	// if (a[x][y]!='0'){
	// 	dfs(x, y+1);
	// 	return;
	// } 

	// if (up[x][y]){
	// 	push(x, y, x, y+1, x, y+2);
	// 	push(x, y, x+1, y, x+1, y-1);
	// 	push(x, y, x+1, y, x+1, y+1);
	// 	push(x, y, x, y+1, x+1, y);
	// }

	// else{
	// 	push(x, y, x, y+1, x, y+2);
	// 	push(x, y, x, y+1, x+1, y+1);
	// }
}

int main(){
	scanf("%d", &n);
	init(n);
	input(n);

	dfs();

	printf("nemoguce\n");
}

Compilation message

trapezi.cpp: In function 'void input(int)':
trapezi.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%s", bufs);
      |   ~~~~~^~~~~~~~~~~~
trapezi.cpp: In function 'int main()':
trapezi.cpp:248:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  248 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 979 ms 556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 23 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 186 ms 564 KB Output is correct
8 Correct 151 ms 572 KB Output is correct
9 Correct 18 ms 576 KB Output is correct
10 Execution timed out 1083 ms 468 KB Time limit exceeded
11 Halted 0 ms 0 KB -