fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef pair<ll, ll> pll;
  6. typedef vector<pll> vpll;
  7. typedef pair<int, int> ii;
  8. typedef vector<int> vi;
  9. typedef vector<ll> vll;
  10. typedef vector<ii> vii;
  11. typedef vector<vi> vvi;
  12. typedef vector<vii> vvii;
  13. typedef map<int, int> mpii;
  14. typedef unordered_map<int, int> umpii;
  15. #define pb(v) push_back(v)
  16.  
  17. int inf = 1e9;
  18. int mod = 1e9 + 7;
  19. double eps = 1e-9;
  20. int dr[] = {-1, 0, 0, 1};
  21. int dc[] = {0, 1, -1, 0};
  22.  
  23. /*...................................................*/
  24.  
  25. int dp[100010][2];
  26.  
  27. int fn(vii &a, int i, int ch, set<int> &markedL, set<int> &markedR, int call)
  28. {
  29.     if (dp[i][ch] != -1)
  30.         return dp[i][ch];
  31.  
  32.     int idx = a[i].second;
  33.     if (!ch)
  34.         markedL.insert(-idx);
  35.     else
  36.         markedR.insert(idx);
  37.  
  38.     int mn = inf, mx = -1;
  39.     if (!markedR.empty())
  40.         mn = *markedR.begin();
  41.  
  42.     if (!markedL.empty())
  43.         mx = -(*markedL.begin());
  44.  
  45.     // cout << "\nRecursive Call: " << call << '\n';
  46.     // cout << "\nIndices which have been marked Left: \n";
  47.     // for(auto it: markedL)
  48.     // cout << it << ' ';
  49.  
  50.     // cout << "\nIndices which have been marked Right: \n";
  51.     // for(auto it: markedR)
  52.     // cout << it << ' ';
  53.     // cout << '\n';
  54.  
  55.     //cout << "mn: " << mn << " mx: " << mx << '\n';
  56.     bool f = 0;
  57.     for (int j = i + 1; !f && j < a.size(); j++)
  58.     {
  59.         int id = a[j].second;
  60.         if (mx < id && id < mn) // check if 'id' has already been marked or not
  61.             f = 1, dp[i][ch] = 1 + min(fn(a, j, 0, markedL, markedR, call + 1), fn(a, j, 1, markedL, markedR, call + 1));
  62.     }
  63.  
  64.     if (!ch)
  65.         markedL.erase(-idx);
  66.     else
  67.         markedR.erase(idx);
  68.  
  69.     if (!f)
  70.         return dp[i][ch] = 1;
  71.     return dp[i][ch];
  72. }
  73. int main()
  74. {
  75.     int t, n, m, i, j;
  76.  
  77.     cin >> t;
  78.     int tc = t;
  79.     while (t--)
  80.     {
  81.         cin >> n;
  82.         vii a(n);
  83.  
  84.         for (i = 0; i < n; i++)
  85.             dp[i][0] = dp[i][1] = -1;
  86.  
  87.         for (i = 0; i < n; i++)
  88.         {
  89.             ll x;
  90.             cin >> x;
  91.             a[i] = {x, i};
  92.         }
  93.  
  94.         sort(a.begin(), a.end(), greater<>());
  95.  
  96.         set<int> sl, sr;
  97.         cout << min(fn(a, 0, 0, sl, sr, 0), fn(a, 0, 1, sl, sr, 0)) << '\n';
  98.     }
  99.     return 0;
  100. }
Time limit exceeded #stdin #stdout 5s 17608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sAcWDf
language:
C++14 (gcc 8.3)
created:
5 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!