Submission #674420

#	Time	Username	Problem	Language	Result	Execution time	Memory
674420		QwertyPi	Costinland (info1cup19_costinland)	C++14	20 / 100	1 ms	212 KiB

costinland

#include <bits/stdc++.h>
#define int long long
using namespace std;

char c[51][51];

void defa(int n, int m){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if((i == n - 1) == (j == m - 1)) c[i][j] = '.';
			else if(i == n - 1) c[i][j] = 'r';
			else c[i][j] = 'd';
		}
	}
}

void pr(int n, int m){
	cout << n << ' ' << m << endl;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cout << c[i][j];
		}
		cout << endl;
	}
}

void part1(int K){
	int n = 0, m = 0;
	if(K <= 5){
		n = 2; m = 5;
		defa(n, m);
		for(int i = 0; i < K - 1; i++){
			c[0][i] = 'X';
		}
		pr(n, m);
	}else if(K <= 8){
		n = 5; m = 5;
		defa(n, m);
		for(int i = 0; i < 4; i++){
			c[0][i] = 'X';
		}
		for(int i = 0; i < K - 4; i++){
			c[i][0] = 'X';
		}
		pr(n, m);
	}else if(K <= 10){
		n = 5; m = 5;
		defa(n, m);
		for(int i = 0; i < 4; i++){
			c[0][i] = 'X';
		}
		for(int i = 0; i < K - 6; i++){
			c[i][0] = 'X';
		}
		c[1][1] = 'X';
		pr(n, m);
	}else if(K <= 12){
		n = 5; m = 5;
		defa(n, m);
		for(int i = 0; i < 4; i++){
			c[0][i] = 'X';
		}
		for(int i = 0; i < K - 8; i++){
			c[i][0] = 'X';
		}
		c[1][1] = 'X';
		c[2][2] = 'X';
		pr(n, m);
	}else if(K <= 16){
		n = 5; m = 5;
		defa(n, m);
		for(int i = 0; i < 3; i++){
			c[0][i] = c[1][i] = 'X';
		}
		K -= 10;
		if(K){
			c[2][min(3LL, K) - 1] = 'X';
			K -= min(3LL, K);
		}
		if(K){
			c[3][min(3LL, K) - 1] = 'X';
			K -= min(3LL, K);
		}
		pr(n, m);
	}else if(K <= 19){
		n = 5; m = 5;
		defa(n, m);
		for(int i = 0; i < 4; i++){
			c[0][i] = c[1][i] = 'X';
		}
		K -= 15;
		if(K){
			c[2][min(4LL, K) - 1] = 'X';
			K -= min(4LL, K);
		}
		if(K){
			c[3][min(4LL, K) - 1] = 'X';
			K -= min(4LL, K);
		}
		pr(n, m);
	}
}

int C(int n, int m){
	double f = 1;
	for(int i = n + 1; i <= n + m; i++) f *= i;
	for(int i = 1; i <= m; i++) f /= i;
	return f;
}
void part2(int K){
	int n = 49, m = 49;
	defa(n, m);
	if(K <= 49){
		for(int i = 0; i < K - 1; i++){
			c[0][i] = 'X';
		}
		pr(n, m);
		return;
	}
	for(int m = 49; m >= 1; m--){
		for(int l = 1;; l++){
			defa(n, m);
			if(K <= C(m - 1, l + 1)){
				K -= C(m - 1, l);
				for(int j = 0; j < l; j++){
					for(int i = 0; i < m - 1; i++){
						c[j][i] = 'X';
					}
				}
				for(int j = 1; j < m - 1; j++){
					for(int k = m - 2; k >= 0; k--){
						if(K >= C(k, l - 1)){
							K -= C(k, l - 1);
							c[j][k] = 'X';
							break;
						}
					}
				}
				if(K == 0) { pr(n, m); return; }
				break;
			}
		}
	}
}

int32_t main(){
	int K; cin >> K;
	if(K <= 19){
		part1(K);
	}else{
		part2(K);
	}
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80