fork download
copy 
  1.  
  2.  
  3. #ifdef Asaad
  4.     #include "cp.h"
  5.     #define debug(...) _dbg_many(#__VA_ARGS__, __VA_ARGS__)
  6.     #define here cerr << "LINE " << __LINE__ << "\n"
  7. #else 
  8.     #include <bits/stdc++.h>
  9.     using namespace std;
  10.     /*
  11.     #include <ext/pb_ds/assoc_container.hpp>
  12.     #include <ext/pb_ds/tree_policy.hpp>
  13.     using namespace __gnu_pbds;
  14.     template<class T>
  15.     using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  16.     */
  17.     #define debug(...) 
  18.     #define here 
  19. #endif
  20.  
  21.  
  22.  
  23. #define ll long long
  24. #define int long long
  25. #define all(x) x.begin(), x.end()
  26. #define siz(x) ((int)x.size())
  27. #define yes cout << "YES\n"
  28. #define no cout << "NO\n"
  29. #define f first
  30. #define s second
  31. #define eb emplace_back
  32. #define pb push_back
  33.  
  34.  
  35. const int mod = 1e9+7;
  36. const int N = 200009;
  37. const long long inf = 1e18+12309138;
  38. double eps = 1e-9;
  39.  
  40. mt19937 rng((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
  41.  
  42. int rnd(int l, int r) {
  43.     return uniform_int_distribution<int>(l, r)(rng);
  44. }
  45.  
  46.  
  47.  
  48.  
  49. int dp[20][2][2][2];
  50. int lockIN(int n, int x){
  51.     //ll n, x;cin>>n>>x;
  52.     if(!n){
  53.         if ( x ) return 1LL;
  54.         return 0LL;
  55.     }memset(dp,-1,sizeof(dp));
  56.     string sl = to_string(n);
  57.     string sr = to_string(x);
  58.     while(sl.size()<sr.size())sl='0'+sl;
  59.     int sz = sl.size();
  60.     auto go =[&](auto&&go,int idx, int ub, int lb, int z){
  61.         if(idx>=sz) return 0LL;
  62.         int lo = lb?sl[idx]-'0':0;
  63.         int hi = ub?sr[idx]-'0':9;
  64.         int&ret=dp[idx][ub][lb][z];
  65.         if(~ret) return ret;
  66.         ret=100;
  67.         for(int i = lo;i<=hi;++i){
  68.             ret=min(ret,(!z&&i==0)+go(go,idx+1,ub&&(i==hi),lb&&(i==lo),z&&(i==0)));
  69.         }
  70.         return ret;
  71.     };
  72.     go(go,0,1,1,1);
  73.     ll res = 0;
  74.     auto build =[&](auto&&build,int idx,int ub, int lb, int z){
  75.         if(idx>=sz) return;
  76.         int lo = lb?sl[idx]-'0':0;
  77.         int hi = ub?sr[idx]-'0':9;
  78.         int ret = dp[idx][ub][lb][z];
  79.         for(int i = lo;i<=hi;++i){
  80.             if(ret==(!z&&i==0)+go(go,idx+1,ub&&(i==hi),lb&&(i==lo),z&&(i==0))){
  81.                 res=res*10+i;
  82.                 build(build,idx+1,ub&&(i==hi),lb&&(i==lo),z&&(i==0));
  83.                 return;
  84.             }
  85.         }
  86.         return;
  87.     };
  88.     build(build,0,1,1,1);
  89.     return res-n;
  90. }
  91.  
  92.  
  93. int bad (int x, int y) {
  94.     //nb=
  95.     //int x, y;
  96.     //cin >> x >> y;
  97.     y-= x;
  98.     if ( x == 0 ) {
  99.     	return min(1LL, y);
  100.     }
  101.     int ans = 0;
  102.     vector<int> pw(19, 1), mo(19, 1);
  103.     for (int i=1; i<19; i++) {
  104.     	pw[i] = pw[i-1]*10;
  105.     	mo[i] = mo[i-1]*10+1;
  106.     }
  107.     for (int i=0; i<19; i++) {
  108.     	int bye = x/pw[i];
  109.     	if ( bye == 0 ) break;
  110.     	if ( bye%10 != 0 ) continue;
  111.     	bye*=pw[i];
  112.     	bye+= mo[i];
  113.     	int hi = min(bye-x, pw[i]+ans);
  114.     	if ( hi <= y ) {
  115.     		ans = hi;
  116.     	} else break;
  117.     }
  118.     return ans;  
  119.  
  120. } 
  121.  
  122.  
  123.  
  124.  
  125. void tc () {
  126.     //nb=
  127.     int x = rnd(0, 1e18);
  128.     int y  = rnd(x, 1e18);
  129.     int a = lockIN(x, y);
  130.     int b = bad(x, y);
  131.     if ( a == b ) return;
  132.     else {
  133.     	cout << "BAD ...\n";
  134.     	cout << x << " " << y << "\n";
  135.     	cout << a << " " << b << "\n";
  136.         exit(0);
  137.     }
  138.  
  139.  
  140.  
  141.  
  142. } 
  143.  
  144.  
  145.  
  146.  
  147.  
  148. signed main () {
  149.     ios::sync_with_stdio(false);
  150.     cin.tie(0);
  151.     //freopen( "input.txt", "r", stdin );
  152.     //freopen( "output.txt", "w", stdout );
  153.     //cout << fixed << setprecision(9);
  154.     //pre();
  155.     int t=1;
  156.     cin >> t;
  157.  
  158.     for (int i=1; i<=t; i++) {
  159.         #ifdef Asaad
  160.             auto start = chrono::high_resolution_clock::now();
  161.             //cout << "---Case " << i << " Start---\n\n";
  162.         #endif
  163.  
  164.         tc();
  165.  
  166.  
  167.         #ifdef Asaad
  168.             auto end = chrono::high_resolution_clock::now();
  169.             //cout << "---Case " << i << " End---\n";
  170.             //if ( i%10000 == 0 )
  171.             //cerr << "Time #" << i << ": " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms" << endl;
  172.             //cout << "--------------\n";
  173.         #endif
  174.     }
  175.     cout << "ALL good\n";
  176. }
  177.  
  178.  
  179.  
  180.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ALL good
https://ideone.com/gUC2jl
language:
C++14 (gcc 8.3)
created:
3 hours 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!