fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define loopf(i, a, b) for (int i = a; i < b; i++)
  5. #define loopb(i, a, b) for (int i = a; i > b; i--)
  6. #define pb push_back
  7. #define fast                          \
  8.     ios_base::sync_with_stdio(false); \
  9.     cin.tie(NULL);
  10. #define ff first
  11. #define ss second
  12. #define vc vector
  13. #define vii vector<int>
  14. #define vll vector<long long>
  15. #define pii pair<int, int>
  16. #define pll pair<ll, ll>
  17. #define mapii map<int, int>
  18. #define mapll map<ll, ll>
  19. #define all(x) x.begin(), x.end()
  20. #define endl "\n"
  21. #define ld long double
  22. #define sz(v) (int)(v.size())
  23. #define len(v) (int)(v.length())
  24. const ll M = 1e9 + 7;
  25.  
  26. void __print(int x) { cerr << x; }
  27. void __print(long x) { cerr << x; }
  28. void __print(long long x) { cerr << x; }
  29. void __print(unsigned x) { cerr << x; }
  30. void __print(unsigned long x) { cerr << x; }
  31. void __print(unsigned long long x) { cerr << x; }
  32. void __print(float x) { cerr << x; }
  33. void __print(double x) { cerr << x; }
  34. void __print(long double x) { cerr << x; }
  35. void __print(char x) { cerr << '\'' << x << '\''; }
  36. void __print(const char *x) { cerr << '\"' << x << '\"'; }
  37. void __print(const string &x) { cerr << '\"' << x << '\"'; }
  38. void __print(bool x) { cerr << (x ? "true" : "false"); }
  39. template <typename T, typename V>
  40. void __print(const pair<T, V> &x)
  41. {
  42.     cerr << '{';
  43.     __print(x.first);
  44.     cerr << ',';
  45.     __print(x.second);
  46.     cerr << '}';
  47. }
  48. template <typename T>
  49. void __print(const T &x)
  50. {
  51.     int f = 0;
  52.     cerr << '{';
  53.     for (auto &i : x)
  54.         cerr << (f++ ? "," : ""), __print(i);
  55.     cerr << "}";
  56. }
  57. void _print() { cerr << "]\n"; }
  58. template <typename T, typename... V>
  59. void _print(T t, V... v)
  60. {
  61.     __print(t);
  62.     if (sizeof...(v))
  63.         cerr << ", ";
  64.     _print(v...);
  65. }
  66. #ifndef ONLINE_JUDGE
  67. #define debug(x...)               \
  68.     cerr << "[" << #x << "] = ["; \
  69.     _print(x)
  70. #else
  71. #define debug(x...)
  72. #endif
  73.  
  74. #define yes1 cout << "YES" << endl
  75. #define no1 cout << "NO" << endl
  76. #define yes2 cout << "Yes" << endl
  77. #define no2 cout << "N0" << endl
  78. #define imax INT_MAX
  79. #define imin INT_MIN
  80. #define lmax LLONG_MAX
  81. #define lmin LLONG_MIN
  82.  
  83. struct node
  84. {
  85.  
  86.     int val;
  87.     node *prev;
  88.     node *next;
  89.     node()
  90.     {
  91.         prev = next = NULL;
  92.     }
  93.     node(node *prev, node *next, int val)
  94.     {
  95.         this->next = next;
  96.         this->prev = prev;
  97.         this->val = val;
  98.     }
  99.  
  100.     int length()
  101.     {
  102.         int cnt = 0;
  103.         node *temp = this;
  104.         while (temp)
  105.         {
  106.             cnt++;
  107.             temp = temp->next;
  108.         }
  109.         return cnt;
  110.     }
  111.  
  112.     void print()
  113.     {
  114.         node *temp = this;
  115.         while (temp)
  116.         {
  117.             cout << temp->val;
  118.             temp = temp->next;
  119.         }
  120.         cout << endl;
  121.     }
  122. };
  123.  
  124. node *head;
  125. node *last;
  126.  
  127. void insert(node *n)
  128. {
  129.     if (head == NULL)
  130.     {
  131.         head = n;
  132.         last = n;
  133.         return;
  134.     }
  135.  
  136.     n->prev = last;
  137.     last->next = n;
  138.     last = last->next;
  139. }
  140.  
  141. void solve()
  142. {
  143.     int n;
  144.     cin >> n;
  145.  
  146.     string s;
  147.     cin >> s;
  148.  
  149.     head = NULL;
  150.     last = NULL;
  151.  
  152.     loopf(i, 0, n)
  153.     {
  154.         node *temp = new node(NULL, NULL, s[i] - '0');
  155.         insert(temp);
  156.     }
  157.  
  158.     unordered_set<node *> v[10];
  159.  
  160.     node *ptr = head;
  161.  
  162.     int prev_len = head->length();
  163.  
  164.     while (ptr->next)
  165.     {
  166.         if (ptr->next->val == (ptr->val + 1) % 10)
  167.         {
  168.             v[ptr->val].insert(ptr);
  169.         }
  170.         ptr = ptr->next;
  171.     }
  172.  
  173.     unordered_map<node *, bool> taken;
  174.     int curr_len = head->length();
  175.  
  176.     while (true)
  177.     {
  178.  
  179.         // debug("YES");
  180.  
  181.         for (int i = 0; i < 10; i++)
  182.         {
  183.             // debug(sz(v[i]));
  184.             if (sz(v[i]) == 0)
  185.                 continue;
  186.             while (sz(v[i]) > 0)
  187.             {
  188.                 node *curr = *(v[i].begin());
  189.                 v[i].erase(v[i].begin());
  190.  
  191.                 if (taken[curr] == false && curr->next && (curr->val + 1) % 10 == curr->next->val)
  192.                 {
  193.                     curr_len--;
  194.                     taken[curr->next] = true;
  195.                     curr->next = curr->next->next;
  196.                     if (curr->next)
  197.                         curr->next->prev = curr;
  198.                 }
  199.                 else
  200.                     continue;
  201.  
  202.                 curr->val = (curr->val + 2) % 10;
  203.  
  204.                 if (curr->prev)
  205.                 {
  206.                     if ((curr->prev->val + 1) % 10 == curr->val)
  207.                     {
  208.                         v[curr->prev->val].insert(curr->prev);
  209.                     }
  210.                 }
  211.                 if (curr->next)
  212.                 {
  213.                     if ((curr->val + 1) % 10 == curr->next->val)
  214.                     {
  215.                         v[curr->val].insert(curr);
  216.                     }
  217.                 }
  218.             }
  219.             // head->print();
  220.         }
  221.  
  222.         if (prev_len == curr_len)
  223.             break;
  224.         prev_len = curr_len;
  225.     }
  226.  
  227.     head->print();
  228. }
  229.  
  230. int main()
  231. {
  232.     fast;
  233.     int t;
  234.     t = 1;
  235.     cin >> t;
  236.     loopf(i, 0, t)
  237.     {
  238.         cout << "Case #" << i + 1 << ": ";
  239.         solve();
  240.     }
  241. }
Success #stdin #stdout 0s 5624KB
comments (?)
stdin
copy 
4
3
012
4
0145
5
00000
11
98765432101
stdout
copy 
Case #1: 22
Case #2: 26
Case #3: 00000
Case #4: 1
https://ideone.com/wV9KLo
language:
C++14 (gcc 8.3)
created:
3 years 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!