oj.uz

Submission #365324

# Submission time Handle Problem Language Result Execution time Memory
365324 2021-02-11T12:58:05 Z Mlxa Costinland (info1cup19_costinland) C++14
100 / 100
 4 ms 392 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct! Your size: 5
2 Correct 1 ms 332 KB Correct! Your size: 5
3 Correct 1 ms 332 KB Correct! Your size: 5
4 Correct 1 ms 332 KB Correct! Your size: 5
5 Correct 1 ms 332 KB Correct! Your size: 5
6 Correct 1 ms 332 KB Correct! Your size: 5
7 Correct 1 ms 332 KB Correct! Your size: 5
8 Correct 1 ms 332 KB Correct! Your size: 5
9 Correct 1 ms 332 KB Correct! Your size: 5

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Correct! Your size: 49
2 Correct 3 ms 392 KB Correct! Your size: 49
3 Correct 3 ms 332 KB Correct! Your size: 49
4 Correct 4 ms 332 KB Correct! Your size: 49
5 Correct 4 ms 332 KB Correct! Your size: 49
6 Correct 4 ms 332 KB Correct! Your size: 49
7 Correct 4 ms 332 KB Correct! Your size: 49
8 Correct 4 ms 332 KB Correct! Your size: 49