oj.uz

Submission #365636

# Submission time Handle Problem Language Result Execution time Memory
365636 2021-02-12T03:37:55 Z amunduzbaev Costinland (info1cup19_costinland) C++14
100 / 100
 4 ms 332 KB 
/** 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.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 300 KB Correct! Your size: 49
2 Correct 3 ms 332 KB Correct! Your size: 49
3 Correct 3 ms 332 KB Correct! Your size: 49
4 Correct 2 ms 332 KB Correct! Your size: 49
5 Correct 2 ms 332 KB Correct! Your size: 49
6 Correct 4 ms 332 KB Correct! Your size: 49
7 Correct 2 ms 332 KB Correct! Your size: 49
8 Correct 2 ms 332 KB Correct! Your size: 49