fork download
copy 
  1. //#pragma GCC optimize("O3", "unroll-loops")
  2. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. //#define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned ll
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rev reverse
  27. #define gcd __gcd
  28. #define pushb push_back
  29. #define popb pop_back
  30. #define pushf push_front
  31. #define popf pop_front
  32. #define mul2x(a, x) a << x
  33. #define div2x(a, x) a >> x
  34. #define lcm(a, b) (a / __gcd(a, b) * b)
  35. #define log_base(x, base) log(x) / log(base)
  36. #define debug clog << "No errors!"; exit(0);
  37. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  38. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  39. #define fors(i, a, b) for (int i = a; i >= b; --i)
  40. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  41. #define pqueue priority_queue
  42. #define sqrt sqrtl
  43. #define popcount __builtin_popcountll
  44. #define BIT(x, i) (x >> i) & 1
  45. #define MASK(x) (1LL << x)
  46. #define want_digit(x) cout << fixed << setprecision(x);
  47. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  48. using namespace std;
  49. const int MOD = 1e9 + 7; // 998244353
  50. const int inf = 1e9;
  51. const ll INF = 1e18;
  52. const int N = 20;
  53.  
  54. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  55. ll random(const ll &L, const ll &R)
  56. {
  57.     return uniform_int_distribution<ll> (L, R) (rng);
  58. }
  59.  
  60. bool compare(const str& a, const str& b)
  61. {
  62.     if (sz(a) != sz(b))
  63.         return sz(a) < sz(b);
  64.     return a <= b;
  65. }
  66.  
  67. str damn(ll k)
  68. {
  69.     queue <pair <str, vector <int>>> q;
  70.  
  71.     vector <int> base(10, 0);
  72.     for (int d = 1; d <= 9; ++d)
  73.     {
  74.         ++base[d];
  75.         q.push(make_pair(to_string(d), base));
  76.         --base[d];
  77.     }
  78.  
  79.     ll m = 0;
  80.  
  81.     while (!q.empty())
  82.     {
  83.         pair <str, vector <int>> curr = q.front(); q.pop();
  84.  
  85.         ++m;
  86.         if (m == k) return curr.fir;
  87.  
  88.         if (sz(curr.fir) == 20) continue;
  89.  
  90.         for (int d = 0; d <= 9; ++d)
  91.         {
  92.             if (curr.sec[d] < 2)
  93.             {
  94.                 ++curr.sec[d];
  95.                 q.push(make_pair(curr.fir + char('0' + d), curr.sec));
  96.                 --curr.sec[d];
  97.             }
  98.         }
  99.     }
  100.  
  101.     return "-1";
  102. }
  103.  
  104. vector <int> operator - (vector <int> v, int x)
  105. {
  106.     --v[x];
  107.     return v;
  108. }
  109.  
  110. vector <int> operator + (vector <int> v, int x)
  111. {
  112.     ++v[x];
  113.     return v;
  114. }
  115.  
  116. ll k;
  117. map <pair <int, vector <int>>, ll> dp;
  118.  
  119. ll calc(int pos, vector <int> v)
  120. {
  121.     if (pos > N) return 1; // Khi đến được vị trí cuối thì mình đã đảm bảo các vị trí trước rồi nên chắc chắn có kết quả
  122.     if (dp.find({pos, v}) != dp.end()) return dp[{pos, v}]; // Nếu đã từng tính rồi thì lấy lại kết quả luôn
  123.  
  124.     bool started = false; // Đã bắt đầu có nghĩa hay chưa?
  125.     forw (i, 0, 9) if (v[i])
  126.     {
  127.         started = true;
  128.         break;
  129.     }
  130.  
  131.     ll ans = 0; // Số lượng số đúng xây được với tiền tố v
  132.     forw (i, 0, 9)
  133.     {
  134.         if (!started && !i) ans += calc(pos + 1, v); // Điền thêm số 0 vô nghĩa
  135.         else
  136.         {
  137.             if (v[i] == 2) continue; // Đạt giới hạn rồi, không thêm nữa
  138.             ans += calc(pos + 1, v + i); // Cộng thêm lượng kết quả khác nhau nếu đi hướng này
  139.         }
  140.  
  141.         if (ans >= k) // Đã đạt đủ tiêu chuẩn để chọn rồi, không cần thêm làm gì (tràn số)
  142.         {
  143.             ans = k;
  144.             break;
  145.         }
  146.     }
  147.     return dp[{pos, v}] = ans; // Memo lại để tái sử dụng nếu cần
  148. }
  149.  
  150. bool started; // Biến lưu
  151. vector <int> cnt(10, 0); // Đếm tần số xuất hiện của các chữ số trong kết quả
  152. str res; // Biến kết quả
  153. void solve()
  154. {
  155.     cin >> k;
  156.     ++k;
  157.     forw (i, 1, 20) // Xây dựng cho từng vị trí
  158.     {
  159.         if (!started) // Nếu chưa có ý nghĩa thì có hướng vô nghĩa tiếp
  160.         {
  161.             ll add = calc(i + 1, cnt); // Không thêm gì cả do thêm một số 0 vô nghĩa
  162.             if (add >= k) // Nếu số kết quả đạt được >= lượng kết quả mình cần thì đi theo hướng này luôn
  163.             {
  164.                 res += '0';
  165.                 continue;
  166.             }
  167.             else k -= add; // Trừ số kết quả khác nhau của hướng này
  168.  
  169.             forw (j, 1, 9) // Điền các chữ số có nghĩa
  170.             {
  171.                 if (cnt[j] == 2) continue; // Đã đạt tới giới hạn thì không có hướng này
  172.                 ll add = calc(i + 1, cnt + j); // Số kết quả khi đi theo hướng này
  173.                 if (add >= k) // Nếu số kết quả đạt được >= lượng kết quả mình cần thì đi theo hướng này luôn
  174.                 {
  175.                     res += char(j + '0'); // Thêm vào chữ số của hướng này
  176.                     started = true; // Đã bắt đầu có nghĩa
  177.                     ++cnt[j]; // Tính thêm 1 chữ số cho chỗ quả
  178.                     break;
  179.                 }
  180.                 else k -= add; // Trừ đi số kết quả không cần
  181.             }
  182.         }
  183.         else // Nếu đã có ý nghĩa từ trước rồi
  184.         {
  185.             forw (j, 0, 9) // Thử điền số từ 0 đến 9 vì bây giờ chữ số nào cũng có nghĩa
  186.             {
  187.                 if (cnt[j] == 2) continue; // Đã đạt tới giới hạn thì không có hướng này
  188.                 ll add = calc(i + 1, cnt + j); // Số kết quả khi đi theo hướng này
  189.                 if (add >= k) // Nếu số kết quả đạt được >= lượng kết quả mình cần thì đi theo hướng này luôn
  190.                 {
  191.                     res += char(j + '0'); // Thêm vào chữ số của hướng này
  192.                     cnt = cnt + j; // Đã bắt đầu có nghĩa
  193.                     break; // Tính thêm 1 chữ số cho chỗ quả
  194.                 }
  195.                 else k -= add; // Trừ đi số kết quả không cần
  196.             }
  197.         }
  198.     }
  199.  
  200.     forw (i, 0, N - 1)
  201.     {
  202.         if (res[i] != '0') // Tránh những chữ số 0 vô nghĩa
  203.         {
  204.             forw (j, i, N - 1) cout << res[j];
  205.             cout << endl;
  206.             break;
  207.         }
  208.     }
  209. }
  210.  
  211. signed main()
  212. {
  213.     ios_base::sync_with_stdio(false), cin.tie(nullptr);
  214.     srand(time(NULL));
  215.     #define name "test"
  216.     /*
  217.     if (fopen(name".INP", "r"))
  218.     {
  219.         freopen(name".INP", "r", stdin);
  220.         freopen(name".OUT", "w", stdout);
  221.     }
  222.     */
  223.     int numTest = 1;
  224. //    cin >> numTest;
  225.     while (numTest--)
  226.     {
  227.         solve();
  228.     }
  229.     return 0;
  230. }
  231.  
Success #stdin #stdout 0s 5328KB
comments (?)
stdin
copy 
2025
stdout
copy 
2073
https://ideone.com/RnsAVw
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!