Submission #1335912

#TimeUsernameProblemLanguageResultExecution timeMemory
1335912finehaveanormalusernameMonster-Go (EGOI25_monstergo)C++20
100 / 100
20 ms30596 KiB
#include <bits/stdc++.h>
using namespace std;

#define vt vector
#define int long long

int choose(int n, int k) {
   int ret = 1;
   for(int i = n - k + 1; i <= n; i++) ret *= i;
   for(int i = 1; i <= k; i++) ret /= i;
   return ret;
}

signed main() {
   int n; cin >> n;
   vt<vt<int>> dp(60,vt<int>(30,1e9));
   vt<vt<vt<vt<int>>>> ans(60,vt<vt<vt<int>>>(30,vt<vt<int>>(60,vt<int>(30))));
   for(int i = 1; i <= 12; i++) {
      for(int j = 1; j <= 12; j++) {
         int ch = choose(i + j, i);
         if(ch <= 50) {
            if(i + j < dp[ch][i]) {
               dp[ch][i] = i + j;
               for(int k = 0; k < ch; k++) {
                  if(k == 0) {
                     for(int l = 0; l < i; l++) {
                        ans[ch][i][k][l] = l;
                     }
                     continue;
                  }
                  for(int l = 0; l < i; l++) {
                     ans[ch][i][k][l] = ans[ch][i][k - 1][l];
                  }
                  for(int l = i - 1; l >= 0; l--) {
                     if(ans[ch][i][k - 1][l] < l + j) {
                        ans[ch][i][k][l] = ans[ch][i][k - 1][l] + 1;
                        for(int m = l + 1; m < i; m++) {
                           ans[ch][i][k][m] = ans[ch][i][k][m - 1] + 1;
                        }
                        break;
                     }
                  }
               }
            }
         }
      }
   }
   for(int i : vt{1, 2, 3, 4, 6}) {
      for(int j = 1; j <= 12; j++) {
         int ch = choose(i + j, i);
         if(ch > 50) continue;
         if((12 / i) * dp[ch][i] < dp[ch][12]) {
            dp[ch][12] = (12 / i) * dp[ch][i];
            for(int k = 0; k < ch; k++) {
               for(int l = 0; l < 12; l++) {
                  ans[ch][12][k][l] = ans[ch][i][k][l % i] + (l / i) * dp[ch][i];
               }
            }
         }
      }
   }
   dp[1][1] = 1;

   for(int i = 1; i <= 50; i++) {
      for(int j = 1; j <= 12; j++) {
         for(int k = 1; k + 1 <= i; k++) {
            if(dp[k][j] + dp[i - k][j] < dp[i][j]) {
               dp[i][j] = dp[k][j] + dp[i - k][j];
               for(int l = 0; l < k; l++) {
                  for(int m = 0; m < j; m++) {
                     ans[i][j][l][m] = ans[k][j][l][m];
                  }
               }
               for(int l = k; l < i; l++) {
                  for(int m = 0; m < j; m++) {
                     ans[i][j][l][m] = dp[k][j] + ans[i - k][j][l - k][m];
                  }
               }
            }
         }
      }
   }
   
   if(n == 1) {
      for(int i = 0; i < 12; i++) cout << i << " ";
      cout << "\n";
      return 0;
   }
   
   for(int i = 0; i < n; i++) {
      for(int j = 0; j < 12; j++) {
         cout << ans[n][12][i][j] << " ";
      }
      cout << "\n";
   }
}
#Verdict Execution timeMemoryGrader output
Fetching results...