Advertisement
Guest User

Untitled

a guest
Oct 16th, 2021
240
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.00 KB | None | 0 0
  1. #ifdef LOCAL
  2. #include <prettyprint.hpp>
  3. #endif
  4. #include<bits/stdc++.h>
  5. #define endl '\n'
  6. #define all(x) x.begin(), x.end()
  7. #define rall(x) x.rbegin(), x.rend()
  8. #define lg2(x) __lg(x)
  9. #define rem_dupl(x) sort(all(x)); x.erase(unique(all(x)), x.end())
  10. using namespace std;
  11.  
  12. typedef long long ll;
  13. typedef long double db;
  14. typedef pair<int,int> ii;
  15. #define x first
  16. #define y second
  17.  
  18. //mt19937 rand32(chrono::steady_clock::now().time_since_epoch().count());
  19. //mt19937_64 rand64(chrono::steady_clock::now().time_since_epoch().count());
  20.  
  21. const db eps = 1e-9;
  22. const int maxn = (int)2e5 + 5;
  23. const ll mod = (int)1e9 + 7; // 998244353
  24.  
  25. int par[maxn][2], n;
  26. db dp[maxn][2], a[maxn];
  27.  
  28. bool choosen[maxn];
  29.  
  30. int main() {
  31.     ios_base::sync_with_stdio(0); cin.tie(0);
  32.     cout.setf(ios::fixed); cout.precision(0);
  33.  
  34.     cin >> n;
  35.     for(int i = 1; i <= n; i++){
  36.         int x; cin >> x;
  37.        
  38.         a[i] = log((db)x);
  39.     }
  40.  
  41.     for(int i = 0; i < 2; i++)
  42.         fill(dp[0], dp[0] + n + 1, LLONG_MIN);
  43.  
  44.     dp[0][0] = 0;
  45.    
  46.     for(int i = 0; i < n; i++){
  47.         if(dp[i][0] != LLONG_MIN){
  48.             if(dp[i+1][0] < dp[i][0]){
  49.                 dp[i+1][0] = dp[i][0];
  50.                 par[i+1][0] = 0;
  51.             }
  52.             if(dp[i+1][1] < dp[i][0] + a[i+1]){
  53.                 dp[i+1][1] = dp[i][0] + a[i+1];
  54.                 par[i+1][1] = 1;
  55.             }
  56.         }
  57.  
  58.         if(dp[i][1] != LLONG_MIN){
  59.             if(dp[i][1] > dp[i+1][1]){
  60.                 dp[i+1][1] = dp[i][1];
  61.                 par[i+1][1] = 0;
  62.             }
  63.             if(dp[i+1][0] < dp[i][1] - a[i+1]){
  64.                 dp[i+1][0] = dp[i][1] - a[i+1];
  65.                 par[i+1][0] = 1;
  66.             }
  67.         }
  68.     }
  69.  
  70.     int last = n;
  71.     int f = 0;
  72.  
  73.     while(last){
  74.         if(par[last][f]){
  75.             choosen[last] = 1;
  76.             f ^= 1;
  77.         }
  78.         last--;
  79.     }
  80.  
  81.     for(int i = 1; i <= n; i++){
  82.         cout << choosen[i] << ' ';
  83.     }
  84.  
  85.    
  86.    
  87.  
  88.    
  89.    
  90.     return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement