oj.uz

답안 #785135

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
785135 2023-07-17T05:56:27 Z 박상훈(#10022) Trapezi (COI17_trapezi) C++17
63 / 100
 6 ms 564 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
char bufs[101], a[101][101];
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++) printf("%c", a[i][j]);
		printf("\n");
	}

	exit(0);
}

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

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

	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;

	a[x1][y1] = a[x2][y2] = a[x3][y3] = '0' + col;
	dfs(x1, y1+1);
	a[x1][y1] = a[x2][y2] = a[x3][y3] = '0';
}

int fail;
void dfs(int x, int y){
	if (fail > 100000){
		printf("nemoguce\n");
		exit(0);
	}
	if (y > R[x]) {dfs(x+1, L[x+1]); return;}
	if (x==n*2 && y==R[x]){
		if (a[x][y]!='0'){
			output(n);
		}

		fail++;
		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);
	}

	fail++;
}

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

	dfs(1, L[1]);

	printf("nemoguce\n");
}

Compilation message

trapezi.cpp: In function 'void input(int)':
trapezi.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%s", bufs);
      |   ~~~~~^~~~~~~~~~~~
trapezi.cpp: In function 'int main()':
trapezi.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |  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 548 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 0 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 0 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 0 ms 468 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

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 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 5 ms 564 KB Output isn't correct
6 Halted 0 ms 0 KB -