SHARE
TWEET

E. Wavy numbers

a guest Oct 16th, 2014 471 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #define _USE_MATH_DEFINES
  3.  
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <algorithm>
  8. #include <cmath>
  9. #include <vector>
  10. #include <string>
  11. #include <cstring>
  12. #include <set>
  13. #include <map>
  14. #include <queue>
  15.  
  16. using namespace std;
  17.  
  18. #pragma comment(linker, "/STACK:128000000")
  19.  
  20. typedef pair<int, int> pii;
  21. typedef long long int64;
  22. typedef vector<int> vi;
  23. typedef vector<vi> vvi;
  24. typedef vector<pii> vpii;
  25. typedef vector<vpii> vvpii;
  26.  
  27. int64 n, k;
  28. vvpii upstream, downstream;
  29. vpii totalup, totaldown;
  30. vi allnumbers;
  31. vi digits;
  32.  
  33. void generate_upstream(int pos, int value, vpii &a)
  34. {
  35.     allnumbers.push_back(value);
  36.    
  37.     if (pos == 7)
  38.     {
  39.         a.push_back(pii((int)(value % n), value));
  40.         digits.pop_back();
  41.         return;
  42.     }
  43.  
  44.     if (pos & 1)
  45.     {
  46.         for (int i = digits.back() + 1; i < 10; ++i)
  47.         {
  48.             digits.push_back(i);
  49.             generate_upstream(pos + 1, value * 10 + i, a);
  50.         }
  51.     } else {
  52.         for (int i = 0; i < digits.back(); ++i)
  53.         {
  54.             digits.push_back(i);
  55.             generate_upstream(pos + 1, value * 10 + i, a);
  56.         }
  57.     }
  58.  
  59.     digits.pop_back();
  60. }
  61.  
  62. void generate_downstream(int pos, int value, vpii &a)
  63. {
  64.     allnumbers.push_back(value);
  65.  
  66.     if (pos == 6)
  67.     {
  68.         upstream[0].push_back(pii((int)(value % n), value));
  69.     }
  70.    
  71.     if (pos == 7)
  72.     {
  73.         a.push_back(pii((int)(value % n), value));
  74.         digits.pop_back();
  75.         return;
  76.     }
  77.  
  78.     if (!(pos & 1))
  79.     {
  80.         for (int i = digits.back() + 1; i < 10; ++i)
  81.         {
  82.             digits.push_back(i);
  83.             generate_downstream(pos + 1, value * 10 + i, a);
  84.         }
  85.     } else {
  86.         for (int i = 0; i < digits.back(); ++i)
  87.         {
  88.             digits.push_back(i);
  89.             generate_downstream(pos + 1, value * 10 + i, a);
  90.         }
  91.     }
  92.  
  93.     digits.pop_back();
  94. }
  95.  
  96. inline int get_total_leftmost(vpii &a, int md, int ind)
  97. {
  98.     pii cur(md, (ind << 26));
  99.     int res = (int)a.size();
  100.     int l = 0, r = res - 1;
  101.     while (l <= r)
  102.     {
  103.         int mid = (l + r) >> 1;
  104.         if (a[mid] >= cur)
  105.         {
  106.             res = mid;
  107.             r = mid - 1;
  108.             continue;
  109.         }
  110.         else
  111.             l = mid + 1;
  112.     }
  113.     if (res == (int)a.size()) return 0;
  114.     if (a[res].first != md) return 0;
  115.     return (a[res].second & 67108863);
  116. }
  117.  
  118. inline int get_total_rightmost(vpii &a, int md, int ind)
  119. {
  120.     pii cur(md, (ind << 26) | 67108863);
  121.     int res = -1;
  122.     int l = 0, r = (int)a.size() - 1;
  123.     while (l <= r)
  124.     {
  125.         int mid = (l + r) >> 1;
  126.         if (a[mid] <= cur)
  127.         {
  128.             res = mid;
  129.             l = mid + 1;
  130.             continue;
  131.         }
  132.         else
  133.             r = mid - 1;
  134.     }
  135.     if (res == -1) return 0;
  136.     if (a[res].first != md) return 0;
  137.     return (a[res].second & 67108863);
  138. }
  139.  
  140. inline int get_leftmost(vpii &a, int md)
  141. {
  142.     int res = -1;  
  143.     int l = 0, r = (int)a.size() - 1;
  144.     while (l <= r)
  145.     {
  146.         int mid = (l + r) >> 1;
  147.         if (a[mid].first == md)
  148.         {
  149.             res = mid;
  150.             r = mid - 1;
  151.             continue;
  152.         }
  153.         if (a[mid].first > md)
  154.             r = mid - 1;
  155.         else
  156.             l = mid + 1;
  157.     }
  158.     return res;
  159. }
  160.  
  161. inline int get_rightmost(vpii &a, int md)
  162. {
  163.     int res = -1;
  164.     int l = 0, r = (int)a.size() - 1;
  165.     while (l <= r)
  166.     {
  167.         int mid = (l + r) >> 1;
  168.         if (a[mid].first == md)
  169.         {
  170.             res = mid;
  171.             l = mid + 1;
  172.             continue;
  173.         }
  174.         if (a[mid].first > md)
  175.             r = mid - 1;
  176.         else
  177.             l = mid + 1;
  178.     }
  179.     return res;
  180. }
  181.  
  182. inline int get_count(vpii &a, int md)
  183. {
  184.     int left_ind = get_leftmost(a, md);
  185.     if (left_ind == -1) return 0;
  186.     int right_ind = get_rightmost(a, md);
  187.     return right_ind - left_ind + 1;
  188. }
  189.  
  190. inline int get_kth(vpii &a, int md, int kvalue)
  191. {
  192.     int left_ind = get_leftmost(a, md);
  193.     return left_ind + kvalue - 1;
  194. }
  195.  
  196. int main()
  197. {
  198.     cin >> n >> k;
  199.  
  200.     upstream.resize(10);
  201.     downstream.resize(10);
  202.     for (int i = 1; i < 10; ++i)
  203.     {
  204.         digits.push_back(i);
  205.         generate_upstream(1, i, upstream[i]);
  206.        
  207.         digits.push_back(i);
  208.         generate_downstream(1, i, downstream[i]);
  209.        
  210.         sort(upstream[i].begin(), upstream[i].end());
  211.         sort(downstream[i].begin(), downstream[i].end());
  212.     }
  213.     sort(upstream[0].begin(), upstream[0].end());
  214.  
  215.     for (int i = 0; i < 10; ++i)
  216.     {
  217.         for (int j = 0; j < (int)upstream[i].size(); ++j)
  218.             totalup.push_back(pii(upstream[i][j].first, (i << 26)));
  219.         for (int j = 0; j < (int)downstream[i].size(); ++j)
  220.             totaldown.push_back(pii(downstream[i][j].first, (i << 26)));
  221.     }
  222.  
  223.     sort(totalup.begin(), totalup.end());
  224.     sort(totaldown.begin(), totaldown.end());
  225.  
  226.     for (int i = 0; i < (int)totalup.size(); ++i)
  227.     {
  228.         ++totalup[i].second;
  229.         if (i && totalup[i].first == totalup[i - 1].first)
  230.             totalup[i].second += (totalup[i - 1].second & 67108863);
  231.     }
  232.  
  233.     for (int i = (int)totaldown.size() - 1; i >= 0; --i)
  234.     {
  235.         ++totaldown[i].second;
  236.         if (i + 1 != (int)totaldown.size() && totaldown[i + 1].first == totaldown[i].first)
  237.             totaldown[i].second += (totaldown[i + 1].second & 67108863);
  238.     }
  239.  
  240.     sort(allnumbers.begin(), allnumbers.end());
  241.  
  242.     for (int i = 0; i < (int)allnumbers.size(); ++i)
  243.     {
  244.         if (i && allnumbers[i] == allnumbers[i - 1]) continue;
  245.         if (allnumbers[i] % n) continue;
  246.         --k;
  247.         if (!k)
  248.         {
  249.             cout << allnumbers[i] << endl;
  250.             return 0;
  251.         }
  252.     }
  253.  
  254.     for (int i = 0; i < (int)allnumbers.size(); ++i)
  255.     {
  256.         if (i && allnumbers[i] == allnumbers[i - 1]) continue;
  257.         int value = allnumbers[i];
  258.         int64 md64 = (n - ((int64)value * 10000000LL) % n) % n;
  259.         if (md64 >= 10000000LL) continue;
  260.         int md = (int)md64;
  261.         if (value < 10)
  262.         {
  263.             for (int i = 0; i < value; ++i)
  264.             {
  265.                 int cnt = get_count(upstream[i], md);
  266.                 if (cnt < k)
  267.                 {
  268.                     k -= cnt;
  269.                     continue;
  270.                 }
  271.                 int ind = get_kth(upstream[i], md, (int)k);
  272.                 int64 res = (int64)value * 10000000LL + (int64)upstream[i][ind].second;
  273.                 cout << res << endl;
  274.                 return 0;
  275.             }
  276.             for (int i = value + 1; i < 10; ++i)
  277.             {
  278.                 int cnt = get_count(downstream[i], md);
  279.                 if (cnt < k)
  280.                 {
  281.                     k -= cnt;
  282.                     continue;
  283.                 }
  284.                 int ind = get_kth(downstream[i], md, (int)k);
  285.                 int64 res = (int64)value * 10000000LL + (int64)downstream[i][ind].second;
  286.                 cout << res << endl;
  287.                 return 0;
  288.             }
  289.             continue;
  290.         }
  291.         int last_digit = value % 10;
  292.         int prelast_digit = (value / 10) % 10;
  293.         if (prelast_digit < last_digit)
  294.         {
  295.             int cnt = get_total_rightmost(totalup, md, last_digit - 1);
  296.  
  297.             if (cnt < k)
  298.             {
  299.                 k -= cnt;
  300.                 continue;
  301.             }
  302.  
  303.             for (int i = 0; i < last_digit; ++i)
  304.             {
  305.                 int cnt = get_count(upstream[i], md);
  306.                 if (cnt < k)
  307.                 {
  308.                     k -= cnt;
  309.                     continue;
  310.                 }
  311.                 int ind = get_kth(upstream[i], md, (int)k);
  312.                 int64 res = (int64)value * 10000000LL + (int64)upstream[i][ind].second;
  313.                 cout << res << endl;
  314.                 return 0;
  315.             }
  316.         } else {
  317.             int cnt = get_total_leftmost(totaldown, md, last_digit + 1);
  318.  
  319.             if (cnt < k)
  320.             {
  321.                 k -= cnt;
  322.                 continue;
  323.             }
  324.            
  325.             for (int i = last_digit + 1; i < 10; ++i)
  326.             {
  327.                 int cnt = get_count(downstream[i], md);
  328.                 if (cnt < k)
  329.                 {
  330.                     k -= cnt;
  331.                     continue;
  332.                 }
  333.                 int ind = get_kth(downstream[i], md, (int)k);
  334.                 int64 res = (int64)value * 10000000LL + (int64)downstream[i][ind].second;
  335.                 cout << res << endl;
  336.                 return 0;
  337.             }
  338.         }
  339.     }
  340.  
  341.     cout << -1 << endl;
  342.  
  343.     return 0;
  344. }
RAW Paste Data
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!
 
Top