/** 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 = 2e3+5;
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 dd[0][0];
}
void solve(int t_case){
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+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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
172 ms |
63224 KB |
Token "X" doesn't correspond to pattern "[Xrd\.]{5}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1095 ms |
63316 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
