Submission #674436

#	Time	Username	Problem	Language	Result	Execution time	Memory
674436		QwertyPi	Costinland (info1cup19_costinland)	C++14	20 / 100	3 ms	4180 KiB

costinland

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

char c[501][501];

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) { if(c[i][j] != 'X') c[i][j] = '.'; }
			else 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);
	}
}

__int128_t C[501][501];

ostream& operator<<(ostream& out, __int128_t x){
	string s; while(x) s.push_back('0' + x % 10), x /= 10;
	reverse(s.begin(), s.end()); return out << s;
}

void part2(int K){
	if(K <= 49){
		int n = 49, m = 49; defa(n, m);
		for(int i = 0; i < K - 1; i++) c[0][i] = 'X';
		pr(n, m); return;
	}
	int m = 49;
	for(int i = 0; i < 48; i++) c[0][i] = 'X'; K -= 49;
	int j = 1;
	for(;; j++){
		for(int k = m - 2; k >= 0; k--){
			if(K >= C[k][0]){
				K -= C[k][0];
				c[j][k] = 'X';
			}
		}
		if(K == 0) break;
		vector<int> v;
		for(int k = 0; k <= m - 2; k++){
			if(c[j][k] == 'X') v.push_back(k);
		}
		for(int i = 0; i + 1 < v.size(); i++){
			C[v[i + 1]][0] += C[v[i]][0];
		}
	}
	int n = j + 2; defa(n, m); pr(n, m);
	return;
}

int32_t main(){
	for(int i = 0; i <= 500; i++){
		C[i][0] = C[0][i] = 1;
	}
	for(int i = 1; i <= 500; i++){
		for(int j = 1; j <= 500; j++){
			C[i][j] = C[i - 1][j] + C[i][j - 1];
		}
	}
	int K; cin >> K;
	if(K <= 19){
		part1(K);
	}else{
		part2(K);
	}
}

Compilation message (stderr)

costinland.cpp: In function 'void part2(long long int)':
costinland.cpp:121:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  121 |  for(int i = 0; i < 48; i++) c[0][i] = 'X'; K -= 49;
      |  ^~~
costinland.cpp:121:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  121 |  for(int i = 0; i < 48; i++) c[0][i] = 'X'; K -= 49;
      |                                             ^
costinland.cpp:135:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |   for(int i = 0; i + 1 < v.size(); i++){
      |                  ~~~~~~^~~~~~~~~~

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