Submission #365324

#	Time	Username	Problem	Language	Result	Execution time	Memory
365324		Mlxa	Costinland (info1cup19_costinland)	C++14	100 / 100	4 ms	392 KiB

costinland

#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N = 52;
const int INF = 4e18;

int C[N][N];

int k;
int n;
char a[N][N];
int dd[N][N], dr[N][N];

int calc() {
	fill_n(dd[0], N * N, 0);
	fill_n(dr[0], N * N, 0);
	for (int i = 0; i < n; ++i) {
		dd[i][n - 1] = dd[n - 1][i] = 1;
		dr[i][n - 1] = dr[n - 1][i] = 1;
	}
	for (int i = n - 2; i >= 0; --i) {
		for (int j = n - 2; j >= 0; --j) {
			if (a[i][j] == '.') {
				dd[i][j] = dd[i + 1][j];
				dr[i][j] = dr[i][j + 1];
			} else if (a[i][j] == 'r') {
				dd[i][j] = dr[i][j] = dr[i][j + 1];
			} else if (a[i][j] == 'd') {
				dd[i][j] = dr[i][j] = dd[i + 1][j];
			} else {
				dd[i][j] = dr[i][j] = dd[i + 1][j] + dr[i][j + 1];
			}
			assert(dd[i][j] < INF && dr[i][j] < INF);
		}
	}
	return dd[0][0];
}

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0); cin.tie(0);
	for (int i = 0; i < N; ++i) {
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; ++j) {
			C[i][j] = min(INF, C[i - 1][j] + C[i - 1][j - 1]);
		}
	}

	cin >> k;
	if (k <= 19) {
		n = 5;
	} else {
		n = 49;
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			a[i][j] = '.';
		}
	}
	a[0][0] = 'X';
	for (int i = 1; i < n - 3; i += 2) {
		a[i][i] = a[i][i + 1] = a[i + 1][i] = a[i + 1][i + 1] = 'X';
		a[i + 2][i] = a[i + 2][i + 1] = 'r';
		a[i][i + 2] = a[i + 1][i + 2] = 'd';
	}
	for (int i = 1; i < n; ++i) {
		a[i][0] = 'd';
		a[0][i] = 'r';
	}
	for (int i = 0; i < n - 1; ++i) {
		a[i][n - 1] = 'd';
		a[n - 1][i] = 'r';
	}
	vector<tuple<int, int, int>> kn;
	auto upd = [&](int i, int j) {
		char old = a[i][j];
		int f0 = calc();
		a[i][j] = 'X';
		int f1 = calc();
		a[i][j] = old;
		kn.emplace_back(f1 - f0, i, j);
	};
	for (int i = 1; i < n - 1; ++i) {
		upd(0, i);
		upd(i, 0);
	}
	sort(kn.rbegin(), kn.rend());
	int least = k - 2;
	for (auto e : kn) {
		int delta, i, j;
		tie(delta, i, j) = e;
		if (least >= delta) {
			least -= delta;
			a[i][j] = 'X';
		}
	}
	assert(calc() == k);
	cout << n << " " << n << endl;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cout << a[i][j];
		}
		cout << endl;
	}
	return 0;
}

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