fork download 
  1. /**
  2.  *   /\_/\
  3.  *  (= ._.)
  4.  *  / >01<\
  5.  *
  6. */
  7.  
  8. #include<bits/stdc++.h>
  9. #define task ""
  10. #define ii pair<int, int>
  11. #define ll long long
  12. #define ld long double
  13. #define fi first
  14. #define se second
  15. #define faster ios_base::sync_with_stdio(NULL); cin.tie(NULL);
  16. #define F if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); }
  17. using namespace std;
  18.  
  19. const int Q = 1e6 + 21;
  20. const int N = 1e3 + 21;
  21. const int LOG = 20;
  22. const int mod = 1e9 + 7;
  23. const int inf = 1e9 + 7;
  24. const int dx[] = {0, 0, 1, -1};
  25. const int dy[] = {1, -1, 0, 0};
  26.  
  27. int n;
  28. int d[Q];
  29.  
  30. const int p[5] = {1, 10, 100, 1000, 10000};
  31. int dif[5][10][2];
  32.  
  33. int cnt[Q];
  34.  
  35. void init()
  36. {
  37.     for(int i = 0; i < 5; i++)
  38.     {
  39.         for(int c = 0; c < 10; c++)
  40.         {
  41.             dif[i][c][0] = (c == 9 ? -9 * p[i] : p[i]);
  42.             dif[i][c][1] = (c == 0 ? 9 * p[i] : -p[i]);
  43.         }
  44.     }
  45. }
  46.  
  47. void solve()
  48. {
  49.     cin >> n;
  50.  
  51.     init();
  52.  
  53.     for(int i = 0; i <= 1e6; i++)
  54.         d[i] = 26;
  55.  
  56.     queue<int> q;
  57.  
  58.     int ans = 25;
  59.  
  60.     for(int i = 1; i <= n; i++)
  61.     {
  62.         string key;
  63.         cin >> key;
  64.  
  65.         int s = 0;
  66.         for(int i = 0; i < 5; i++)
  67.             s = s * 10 + (key[i] - '0');
  68.  
  69.         cnt[d[s]]--;
  70.         cnt[0]++;
  71.  
  72.         d[s] = 0;
  73.  
  74.         q.push(s);
  75.  
  76.         while(q.size())
  77.         {
  78.             int u = q.front();
  79.             q.pop();
  80.  
  81.             int temp = u;
  82.  
  83.             for(int i = 0; i < 5; i++)
  84.             {
  85.                 int c = temp % 10;
  86.                 temp /= 10;
  87.  
  88.                 for(int dir = 0; dir < 2; dir++)
  89.                 {
  90.                     int v = u + dif[i][c][dir];
  91.  
  92.                     if(d[v] > d[u] + 1)
  93.                     {
  94.                         cnt[d[v]]--;
  95.  
  96.                         d[v] = d[u] + 1;
  97.                         q.push(v);
  98.  
  99.                         cnt[d[v]]++;
  100.                     }
  101.                 }
  102.             }
  103.         }
  104.  
  105.         while(ans > 0 && cnt[ans] == 0)
  106.             ans--;
  107.  
  108.         cout << ans << " " << cnt[ans];
  109.         cout << '\n';
  110.     }
  111. }
  112.  
  113. signed main()
  114. {
  115.     faster;
  116.     F;
  117.  
  118.     int test = 1;
  119.  
  120. //    cin >> test;
  121.  
  122.     while(test--)
  123.     {
  124.         solve();
  125.     }
  126.  
  127.     cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
  128.  
  129.     return 0;
  130. }
  131.  
  132.  
Success #stdin #stdout #stderr 0.01s 8996KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
Time elapsed: 0.007444 s.
https://ideone.com/fT6sOQ
language:
C++ (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!