Submission #923107

#	Time	Username	Problem	Language	Result	Execution time	Memory
923107		Ianis	Costinland (info1cup19_costinland)	C++17	20 / 100	10 ms	348 KiB

costinland

#ifdef LOCAL
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <random>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#else
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define cerr if (false) cerr 
#define endl '\n'
#endif

#define fi first
#define se second

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))

#define bit(mask, i) (((mask) >> (i)) & 1)
#define popcount(x) __builtin_popcount(x)

#define YES cout << "YES" << endl
#define NO cout << "NO" << endl

using namespace std;

template <typename T>
bool ckmax(T &a, T b) { return a < b ? a = b, true : false; }
template <typename T>
bool ckmin(T &a, T b) { return a > b ? a = b, true : false; }

#define int __int128_t

using pii = pair<int, int>;

int64_t n, m, k;
char a[55][55];
int dpd[55][55], dpr[55][55];

ostream &operator<<(ostream &out, int x) {
   string s;
   if (x == 0) {
      out << 0;
      return out;
   }
   while (x) {
      s.push_back((x % 10) + '0');
      x /= 10;
   }
   reverse(all(s));
   out << s;
   return out;
}

int calc() {
   dpd[0][1] = 1;
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         if (a[i][j] == 'X') {
            dpd[i][j] = dpr[i][j] = dpd[i - 1][j] + dpr[i][j - 1];
         } else if (a[i][j] == 'r') {
            dpr[i][j] = dpd[i - 1][j] + dpr[i][j - 1];
            dpd[i][j] = 0;
         } else if (a[i][j] == 'd') {
            dpd[i][j] = dpd[i - 1][j] + dpr[i][j - 1];
            dpr[i][j] = 0;
         } else {
            dpd[i][j] = dpd[i - 1][j];
            dpr[i][j] = dpr[i][j - 1];
         }
      }
   }

   return dpd[n][m] + dpr[n][m];
}

void solve() {
   if (k <= 19)
      n = m = 5;
   else
      n = m = 49;

   for (int i = 1; i < n; i++) {
      for (int j = 1; j < m; j++)
         a[i][j] = '.';
   }

   for (int i = 1; i <= n; i++)
      a[i][m] = 'd';
   for (int j = 1; j <= m; j++)
      a[n][j] = 'r';
   a[n][m] = '.';

   for (int i = 1; i < n; i++) {
      for (int j = 1; j < m; j++) {
         a[i][j] = 'X';
         if (calc() > k) a[i][j] = '.';
      }
   }

   cout << n << ' ' << m << endl;
   for (int i = 1; i <= n; i++) {
      cout << (a[i] + 1) << endl;
   }

   if (calc() != k) exit(69);
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#endif
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   
   cin >> k;
   solve();

   return 0;
}

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