제출 #1318490

#제출 시각아이디문제언어결과실행 시간메모리
1318490Jawad_Akbar_JJCostinland (info1cup19_costinland)C++20
100 / 100
1 ms332 KiB
#include <iostream>
#include <map>

using namespace std;
#define int long long
char a[100][100], num[100][100];

int solve(int n){
	int sm = 0;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++)
			num[i][j] = 0;
	}

	num[1][1] = 1;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (a[i][j] != 'X')
				continue;
			int I = i+1, J = j + 1;
			while (I <= n and a[I][j] != 'X')
				I++;
			num[I][j] += num[i][j];
			if (I > n)
				sm += num[i][j];

			while (J <= n and a[i][J] != 'X')
				J++;
			num[i][J] += num[i][j];
			if (J > n)
				sm += num[i][j];

		}
	}
	return sm;
}

void solve1(int K){
	int nn = 16, n = 4;

	for (int i=0;i<(1<<nn);i++){
		for (int j=0, r = 1, c = 1;j<nn;j++){
			if ((1<<j) & i)
				a[r][c] = 'X';
			else
				a[r][c] = '.';
			if (c == n)
				r++, c = 0;
			c++;
		}

		int sm = solve(n);
		if (sm == 0){
			sm = 1;
			a[1][1] = 'r';
		}
		if (sm == K){
			n = 5;
			for (int i=1;i<=n;i++)
				a[i][n] = 'd', a[n][i] = 'r';
			a[n][n] = '.';
	
			cout<<"5 5\n";			
			for (int j=1;j<=n;j++){
				for (int k=1;k<=n;k++)
					cout<<a[j][k];
				cout<<'\n';
			}
			cout<<'\n';
			exit(0);
		}
	}
}

signed main(){
	int n = 49, N;
	cin>>N;

	if (N <= 19){
		solve1(N);
	}

	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (i < 3)
				a[i][j] = '.';
			else if (i == j)
				a[i][j] = 'X';
			else if (i-1 == j and i % 2 == 0)
				a[i][j] = 'X';
			else if (j - 1 == i and j % 2 == 0)
				a[i][j] = 'X';
			else
				a[i][j] = '.';
		}
	}

	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (a[i][j] == '.' and i > 1 and a[i-1][j] == 'X')
				a[i][j] = 'r';
			if (i == n)
				a[i][j] = 'r';
			if (a[i][j] == '.' and j > 1 and a[i][j-1] == 'X')
				a[i][j] = 'd';
			if (j == n)
				a[i][j] = 'd';
		}
	}

	string s;
	while (N){
		s = char(N % 6 + '0') + s;
		N /= 6;
	}

	for (int i=n, fl = 0, j = s.size() - 1;j >= 0;i -= 2, j--){
		if (s[j] == '0')
			continue;
		if (s[j] == '1'){
			a[1][i] = 'X';
		}
		else if (s[j] == '2'){
			a[1][i] = a[1][i-1] = 'X';
			a[2][i-1] = 'r';
			a[2][i] = 'd';
		}
		else if (s[j] == '3'){
			a[1][i-1] = 'X';
		}
		else if (s[j] == '4'){
			a[1][i-1] = a[2][i-1] = 'X';
			a[2][i] = 'd';
		}
		else if (s[j] == '5'){
			a[1][i] = a[1][i-1] = 'X';
			a[2][i-1] = 'X';
			a[2][i] = 'd'; 
		}

		if (fl == 0){
			if (a[1][i] == 'X')
				a[1][i] = 'd';
			else if (a[1][i-1] == 'X')
				a[1][i-1] = 'd';
			fl = 1;
		}
	}

	a[1][1] = 'r';
	a[n][n] = '.';
	cout<<n<<" "<<n<<endl;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++)
			cout<<a[i][j];
		cout<<'\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...