oj.uz

Submission #785334

# Submission time Handle Problem Language Result Execution time Memory
785334 2023-07-17T08:29:09 Z 박상훈(#10022) Trapezi (COI17_trapezi) C++17
63 / 100
 500 ms 468 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(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] = (++cntC) + '0';
	dfs(x1, y1+1);
	--cntC;
	a[x1][y1] = a[x2][y2] = a[x3][y3] = '0';
}

void dfs(int x, int y){
	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(1, L[1]);

	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:143:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 Correct 1 ms 468 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory 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 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory 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 0 ms 468 KB Output is correct
5 Execution timed out 1080 ms 468 KB Time limit exceeded
6 Halted 0 ms 0 KB -