API tools faq
paste
Advertisement
prog3r

Nicee

prog3r
Jun 28th, 2025
132
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.76 KB | None | 0 0
raw download clone embed print report
  1. //#include "testlib.h"
  2. #include <bits/extc++.h>
  3. using namespace std;
  4. using namespace __gnu_pbds;
  5. template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  6. #define int long long
  7. #define YES(x) cout << (x?"YES\n":"NO\n")
  8. #define NO(x) cout << (x?"NO\n":"YES\n")
  9. #ifdef LO
  10. #pragma GCC optimize("trapv")
  11. #endif
  12. #ifndef LO
  13. #pragma GCC optimize("Ofast,unroll-loops")
  14. #endif
  15. //constexpr int MOD = (119<<23)+1;
  16. //constexpr int MOD = 967276608647009887ll;
  17. //constexpr int MOD = 1e9+7;
  18. constexpr int INF = 1e18;
  19. signed main() {
  20. #ifndef LO
  21.     clog << "FIO\n";
  22.     ios::sync_with_stdio(0);
  23.     cin.tie(0);
  24. #endif
  25. #ifdef LO
  26.     cout << unitbuf;
  27. #endif
  28.     auto fenw_ops = [&] (const int x) -> int {
  29.         if (x <= 1) {
  30.             assert(false);
  31.         }
  32.         return __lg(x-1)+2;
  33.     };
  34.     int N = 1000;
  35.     vector<int> dp(N+1);
  36.     dp[0] = 0;
  37.     dp[1] = 1;
  38.     vector<pair<int,int>> ch(N+1);
  39.     vector<int> palka(N+1);
  40.     for (int i = 2; i <= N; i += 1) {
  41.         for (int use = 1; use <= i; use += 1) {
  42.             for (int one = 0; i-use-one >= one; one += 1) {
  43.                 int another = i-use-one;
  44.                 if (!one) {
  45.                     int x = dp[another];
  46.                     if (dp[i] < x) {
  47.                         ch[i] = {one, another};
  48.                         palka[i] = use;
  49.                     }
  50.                     dp[i] = max(dp[i], x);
  51.                 } else {
  52.                     int x = min({max(dp[one]+1, dp[another]+1),
  53.                                  max(dp[one]+min(use, fenw_ops(use+1)), dp[another]+0),
  54.                                  max(dp[one]+0, dp[another]+min(use, fenw_ops(use+1)))});
  55.                     if (dp[i] < x) {
  56.                         ch[i] = {one, another};
  57.                         palka[i] = use;
  58.                     }
  59.                     dp[i] = max(dp[i], x);
  60.                 }
  61.             }
  62.         }
  63.         cout << "(" << i << ", " << dp[i] << ")\n";
  64. //        cout << "(" << i << ", " << dp[i] << " " << ch[i].first << "|" << dp[ch[i].first] << " " << ch[i].second << "|" << dp[ch[i].second] << "), " << palka[i] << "\n";
  65.     }
  66.     int curr = 1;
  67.     auto print = [&] (auto f, const int x) -> int {
  68.         if (!x) {
  69.             return -1;
  70.         }
  71.         int U = curr++;
  72.         int u = U;
  73.         for (int i = 0; i < palka[x]-1; i += 1) {
  74.             int v = curr++;
  75.             cout << u << " " << v << "\n";
  76.             u = v;
  77.         }
  78.         int v1 = f(f, ch[x].first), v2 = f(f, ch[x].second);
  79.         if (v1 != -1) {
  80.             cout << u << " " << v1 << "\n";
  81.         }
  82.         if (v2 != -1) {
  83.             cout << u << " " << v2 << "\n";
  84.         }
  85.         return U;
  86.     };
  87. //    print(print, N);
  88.  
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!