Submission #365636

#	Time	Username	Problem	Language	Result	Execution time	Memory
365636		amunduzbaev	Costinland (info1cup19_costinland)	C++14	100 / 100	4 ms	332 KiB

costinland

/** made by amunduzbaev **/
#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
 
const int N = 55;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
 
#define MULTI 0
 
int n, m, k, ans, res;
int dd[N][N], dr[N][N];
char a[N][N];
 
int calc(){
	memset(dd, 0, sizeof dd);
	memset(dr, 0, sizeof dr);
	
	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];
			}
		}
	}
	return dr[0][0];
}

int rd(){
	int res = 0;
	char ch; ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	} res = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		res = res*10 + (ch - '0');
	} return res; 
}

void solve(int t_case){
	k = rd();
	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+1][i] = a[i][i+1] = a[i+1][i+1] = 'X';
		a[i+1][i+2] = a[i][i+2] = 'd';
		a[i+2][i+1] = a[i+2][i] = 'r';
	}
	
	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';
	
	
	vv<ipii> tt;
	auto upd = [&](int i, int j){
		int f0 = calc();
		char old = a[i][j];
		a[i][j] = 'X';
		int f1 = calc();
		a[i][j] = old;
		tt.pb({f1 - f0, {i, j}});
	};
	
	for(int i=0;i<n-1;i++){
		upd(i, 0);
		upd(0, i);
	}
	
	sort(rall(tt));
	int last = k-2;
	for(auto x:tt){
		int cur, i, j;
		cur = x.ff, tie(i, j) = x.ss;
		if(last >= cur){
			last -= cur;
			a[i][j] = 'X';
		}
	}
	assert(calc() == k);
	cout<<n<<" "<<n<<"\n";
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++) cout<<a[i][j];
		cout<<"\n";
	}
	cout<<"\n";
}
	
signed main(){
	NeedForSpeed
	if(!MULTI) {
		solve(1);
	} else {
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	}
	return 0;
}

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