daily pastebin goal
19%
SHARE
TWEET

Untitled

raliev May 29th, 2012 760 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <assert.h>
  7.  
  8. using namespace std;
  9.  
  10. const long double log_2 = 1.584962500721156;
  11.  
  12. vector<int> power[4];
  13. vector<int> ans, a, parent;
  14.  
  15. bool check(int pos, int cnt)
  16. {
  17.         bool f = true;
  18.         for (int i = pos - cnt + 1; i < pos; i++)
  19.                 if (a[i] < a[i + 1])f = false;
  20.         if (f) return true;
  21.  
  22.         f = true;
  23.         for (int i = pos - cnt + 1; i < pos; i++)
  24.                 if (a[i] > a[i + 1])f = false;
  25.         return f;
  26. }
  27.  
  28. bool comp(int i, int j)
  29. {
  30.         int x1 = power[2][i], x2 = power[2][i - j];
  31.         int y1 = power[3][i], y2 = power[3][i - j];
  32.         if (j == 2) x2++;
  33.         else y2++;
  34.         if (x1 < x2 && y1 < y2)
  35.                 return true;
  36.         if (x1 >= x2 && y1 >= y2)
  37.                 return false;
  38.         int t =  min(x1, x2);
  39.         x1 -= t; x2 -= t;
  40.         t = min(y1, y2);
  41.         y1 -= t; y2 -= t;
  42.         if (x1 == 0) return y1 * log_2 < x2;
  43.         else return x1 < log_2 * y2;
  44. }
  45.  
  46. int main()
  47. {
  48.         //freopen("monotone.in", "r", stdin);
  49.         //freopen("monotone.out", "w", stdout);
  50.         int n;
  51.         cin >> n;
  52.         assert( 1 <= n && n <= 0.5e5);
  53.         a.resize(n + 1);
  54.         for (int i = 1; i <= n; i++)
  55.         {
  56.                 cin >> a[i];
  57.                 assert(0 <= a[i] && a[i] <= 1e9);
  58.         }
  59.         parent.resize(n + 1);
  60.         power[2].resize(n + 1);
  61.         power[3].resize(n + 1);
  62.         power[2][2] = 1;
  63.         for (int i = 3; i <= n; i++)
  64.         {
  65.                 power[3][i] = power[3][i - 1]; power[2][i] = power[2][i - 1];
  66.                 parent[i] = i - 1;
  67.                 for (int j = 2; j < 4; j++)
  68.                         if (check(i, j))
  69.                                 if (comp(i, j))
  70.                                 {
  71.                                         power[5 - j][i] = power[5 - j][i - j];
  72.                                         power[j][i] = power[j][i - j] + 1;
  73.                                         parent[i] = i - j;
  74.                                 }
  75.         }
  76.         int t = n;
  77.         while (t > 0)
  78.         {
  79.                 ans.push_back(t);
  80.                 t = parent[t];
  81.         }
  82.         reverse(ans.begin(), ans.end());
  83.         cout << ans.size() << "\n";
  84.         for (int i = 0; i < ans.size(); i++)
  85.                 cout << ans[i] << ((i == ans.size() - 1) ? "\n" : " ");
  86. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top