fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <stack>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <deque>
  7.  
  8. using namespace std;
  9.  
  10. #define maxN 20007
  11.  
  12. int a[maxN];
  13.  
  14. int n;
  15.  
  16. struct op
  17. {
  18.     int curL;
  19.     int curR;
  20.     bool curAsc;
  21. };
  22.  
  23. vector<op>allOp[20];
  24. int cntLayer = 1;
  25.  
  26. void readData()
  27. {
  28.     cin >> n;
  29.     for(int i = 1; i <= n; i++)
  30.         cin >> a[i];
  31. }
  32.  
  33. void gen()
  34. {
  35.     op temp;
  36.     temp.curL = 1;
  37.     temp.curR = n;
  38.     temp.curAsc = false;
  39.     allOp[1].push_back(temp);
  40.     if(n == 1)
  41.         return;
  42.     bool nextLayer = true;
  43.     for(int i = 2; i < 20; i++)
  44.     {
  45.         cntLayer = i;
  46.         for(int j = 0; j < allOp[i-1].size(); j++)
  47.         {
  48.             int mid = (allOp[i-1][j].curL+allOp[i-1][j].curR)/2;
  49.             temp.curL = allOp[i-1][j].curL;
  50.             temp.curR = mid;
  51.             temp.curAsc = 1-allOp[i-1][j].curAsc;
  52.             if(temp.curR-temp.curL == 0)
  53.                 nextLayer = false;
  54.             allOp[i].push_back(temp);
  55.             temp.curL = mid+1;
  56.             temp.curR = allOp[i-1][j].curR;
  57.             temp.curAsc = allOp[i-1][j].curAsc;
  58.             allOp[i].push_back(temp);
  59.             if(temp.curR-temp.curL == 0)
  60.                 nextLayer = false;
  61.         }
  62.         if(!nextLayer)
  63.             return;
  64.     }
  65. }
  66.  
  67. void solve()
  68. {
  69.     /*for(int i = 1; i < 20; i++)
  70.     {
  71.         for(int j = 0; j < allOp[i].size(); j++)
  72.         {
  73.             cout << allOp[i][j].curL << " " <<allOp[i][j].curR << " ";
  74.             if(allOp[i][j].curAsc)
  75.                 cout << "ASC\n";
  76.             else cout << "DESC\n";
  77.         }
  78.         cout << "\n";
  79.     }*/
  80.     deque<int>cur;
  81.     for(int i = 1; i <= n; i++)
  82.     {
  83.         cur.push_back(a[i]);
  84.         cout << "C";
  85.     }
  86.     deque<int>curInS;
  87.     deque<int>curInQ;
  88.     op temp;
  89.     for(int i = 19; i >= 1; i--)
  90.     {
  91.         for(int j = 0; j < allOp[i].size(); j++)
  92.         {
  93.             temp = allOp[i][j];
  94.             if(temp.curL == temp.curR)
  95.             {
  96.                 cout << "HC";
  97.                 cur.push_back(cur.front());
  98.                 cur.pop_front();
  99.                 continue;
  100.             }
  101.             int mid = (temp.curL+temp.curR)/2;
  102.             for(int k = temp.curL; k <= mid; k++)
  103.             {
  104.                 cout << "H";
  105.                 curInS.push_back(cur.front());
  106.                 cur.pop_front();
  107.             }
  108.             for(int k = mid+1; k <= temp.curR; k++)
  109.             {
  110.                 curInQ.push_back(cur.front());
  111.                 cur.pop_front();
  112.             }
  113.             while(!curInS.empty() || !curInQ.empty())
  114.             {
  115.                 if(!curInS.empty() && curInQ.empty())
  116.                 {
  117.                     cout << "C";
  118.                     cur.push_back(curInS.back());
  119.                     curInS.pop_back();
  120.                 }
  121.                 else if(curInS.empty() && !curInQ.empty())
  122.                 {
  123.                     cout << "HC";
  124.                     cur.push_back(curInQ.front());
  125.                     curInQ.pop_front();
  126.                 }
  127.                 else
  128.                 {
  129.                     int addType = 0; //0 - stack, 1 - queue
  130.                     if(temp.curAsc)
  131.                     {
  132.                         if(curInQ.front() < curInS.back())
  133.                             addType = 1;
  134.                     }
  135.                     else if(curInQ.front() > curInS.back())
  136.                         addType = 1;
  137.                     if(addType == 0)
  138.                     {
  139.                         cout << "C";
  140.                         cur.push_back(curInS.back());
  141.                         curInS.pop_back();
  142.                     }
  143.                     else
  144.                     {
  145.                         cout << "HC";
  146.                         cur.push_back(curInQ.front());
  147.                         curInQ.pop_front();
  148.                     }
  149.                 }
  150.             }
  151.         }
  152.     }
  153.     for(int i = 1; i <= n; i++) cout << "H";
  154. }
  155.  
  156. int main()
  157. {
  158.     ios_base::sync_with_stdio(0);
  159.     cin.tie(0);
  160.     readData();
  161.     gen();
  162.     solve();
  163.     return 0;
  164. }
  165.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
4
3 2 1 4
stdout
copy 
CCCCHCHCHCHCHHCCHHCCHHHCCCHCHHHH
https://ideone.com/GKvRqX
language:
C++14 (gcc 8.3)
created:
8 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!