Dang_Quan_10_Tin

THT Sơ Khảo C (2021) seq

Oct 16th, 2021
481
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6.  
  7. constexpr int N = 2e1 + 5;
  8. constexpr ll Inf = 1e17;
  9.  
  10. ll p, k;
  11. ll dp[N][2], g[N][2];
  12. vector<int> s;
  13.  
  14. void Read()
  15. {
  16.     cin >> k >> p;
  17. }
  18.  
  19. void Convert(vector<int> &s, ll v)
  20. {
  21.     s.clear();
  22.     while (v)
  23.     {
  24.         s.emplace_back(v % 10);
  25.         v /= 10;
  26.     }
  27.     reverse(s.begin(), s.end());
  28. }
  29.  
  30. bool HaveNine(ll v)
  31. {
  32.     while (v)
  33.     {
  34.         if (v % 10 == 9)
  35.             return true;
  36.         v /= 10;
  37.     }
  38.     return false;
  39. }
  40.  
  41. pair<vector<int>, ll> Greedy(ll l, ll r)
  42. {
  43.     vector<int> s, tmp;
  44.     ll ans(0);
  45.     for (; l <= r; ++l)
  46.     {
  47.         Convert(tmp, l);
  48.         for (auto i : tmp)
  49.         {
  50.             while (!s.empty() && s.back() < i)
  51.             {
  52.                 s.pop_back();
  53.                 ++ans;
  54.             }
  55.             s.emplace_back(i);
  56.         }
  57.     }
  58.     return make_pair(s, ans);
  59. }
  60.  
  61. ll Pow(ll a, ll b)
  62. {
  63.     ll ans(1);
  64.     for (; b; b >>= 1)
  65.     {
  66.         if (b & 1)
  67.             ans = ans * a;
  68.         a = a * a;
  69.     }
  70.     return ans;
  71. }
  72.  
  73. int getLog(ll v)
  74. {
  75.     int ans(0);
  76.     for (; v >= 10; ++ans, v /= 10)
  77.         ;
  78.     return ans;
  79. }
  80.  
  81. ll Get(ll v)
  82. {
  83.     ll ans(0);
  84.  
  85.     while (1)
  86.     {
  87.         if (v == 0)
  88.             break;
  89.  
  90.         int lg = getLog(v);
  91.  
  92.         ll tmp = Pow(10, lg);
  93.         ans += (lg + 1) * (v - tmp + 1);
  94.         v = tmp - 1;
  95.     }
  96.  
  97.     return ans;
  98. }
  99.  
  100. ll f(int i, bool ok)
  101. {
  102.     if (dp[i][ok] != -1)
  103.         return dp[i][ok];
  104.  
  105.     if (i == (int)s.size())
  106.     {
  107.         if (ok)
  108.         {
  109.             g[i][ok] = 1;
  110.             return dp[i][ok] = 0;
  111.         }
  112.         else
  113.         {
  114.             g[i][ok] = 0;
  115.             return dp[i][ok] = 0;
  116.         }
  117.     }
  118.  
  119.     dp[i][ok] = 0;
  120.     g[i][ok] = 0;
  121.  
  122.     for (int j = 0; j < 10; ++j)
  123.         if (ok || j <= s[i])
  124.         {
  125.             dp[i][ok] += f(i + 1, ok || (j < s[i]));
  126.             if (j == 9)
  127.                 dp[i][ok] += g[i + 1][ok || (j < s[i])];
  128.             g[i][ok] += g[i + 1][ok || (j < s[i])];
  129.         }
  130.  
  131.     return dp[i][ok];
  132. }
  133.  
  134. bool Check(ll v)
  135. {
  136.     memset(dp, -1, sizeof dp);
  137.     memset(g, 0, sizeof g);
  138.  
  139.     ll cnt(0);
  140.     ll x = v;
  141.     while (x > 1 && !HaveNine(x))
  142.         --x;
  143.  
  144.     Convert(s, x);
  145.     cnt += Get(x - 1) - f(0, 0);
  146.  
  147.     cnt += Greedy(x, v).second;
  148.     return cnt < k;
  149. }
  150.  
  151. void Solve()
  152. {
  153.     ll l = 1, m, h = 1e14;
  154.     while (l <= h)
  155.     {
  156.         m = (l + h) / 2;
  157.         if (Check(m))
  158.             l = m + 1;
  159.         else
  160.             h = m - 1;
  161.     }
  162.  
  163.     ll x = l - HaveNine(l);
  164.     while (x > 1 && !HaveNine(x))
  165.         --x;
  166.  
  167.     memset(dp, -1, sizeof dp);
  168.     Convert(s, x);
  169.  
  170.     if (p <= f(0, 0))
  171.     {
  172.         cout << "9\n";
  173.         return;
  174.     }
  175.  
  176.     ll r = k - (Get(x - 1) - f(0, 0));
  177.  
  178.     vector<int> t, tmp;
  179.  
  180.     for (ll i = x; i <= l; ++i)
  181.     {
  182.         Convert(tmp, i);
  183.         for (auto i : tmp)
  184.         {
  185.             while (r > 0 && !t.empty() && t.back() < i)
  186.             {
  187.                 --r;
  188.                 t.pop_back();
  189.             }
  190.             t.emplace_back(i);
  191.         }
  192.     }
  193.  
  194.     if (p <= f(0, 0) + (ll)t.size())
  195.     {
  196.         cout << t[p - f(0, 0) - 1] << "\n";
  197.         return;
  198.     }
  199.  
  200.     //cout << l << " " << f(0, 0) << "\n";
  201.  
  202.     ll digits = Get(l);
  203.  
  204.     p -= f(0, 0) + t.size();
  205.  
  206.     l = l + 1, h = 1e17;
  207.  
  208.     while (l <= h)
  209.     {
  210.         m = (l + h) / 2;
  211.         if (Get(m) - digits < p)
  212.             l = m + 1;
  213.         else
  214.             h = m - 1;
  215.     }
  216.  
  217.     p -= Get(h) - digits;
  218.  
  219.     t.clear();
  220.     for (ll v = l; v; v /= 10)
  221.         t.emplace_back(v % 10);
  222.     reverse(t.begin(), t.end());
  223.  
  224.     cout << t[p - 1] << "\n";
  225. }
  226.  
  227. int32_t main()
  228. {
  229.     ios::sync_with_stdio(0);
  230.     cin.tie(0);
  231.     cout.tie(0);
  232.     int t(1);
  233.     cin >> t;
  234.     for (int _ = 1; _ <= t; ++_)
  235.     {
  236.         Read();
  237.         Solve();
  238.     }
  239. }
RAW Paste Data