提出 #26596785

---

ソースコード 拡げる

#pragma GCC optimize("O2")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pi;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define FORV(i,a,b) for (uint i = a; i < b; i++)
#define FORN(i,a,b) for (int i = a; i <= b; i++)

#define ALL(v) v.begin(), v.end()
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))

#define maxInt INT_MAX
#define maxll LLONG_MAX


double DP[200003][2];
bool res[200003];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n;
  cin >> n;

  vi as;
  as.pb(1);
  FOR(i,0,n){
    int k;
    cin >> k;
    as.push_back(k);
  }

  DP[0][0] = 1.;
  DP[0][1] = 0.;
  FOR(i,1,n+1){
    DP[i][0] = max(DP[i-1][0], DP[i-1][1] / double(as[i]));
    DP[i][1] = max(DP[i-1][1], DP[i-1][0] * double(as[i]));

    if (DP[i][0] > 1e100) {
      DP[i][0] /= 1e90;
      DP[i][1] /= 1e90;
    }
  }


  //   FOR(i,0,n+1){
  //     cout << DP[i][0] << " " << DP[i][1] << endl;
  // }


  bool gold = true;
  for(int i=n-1; i >= 0; i--){
    if (gold){
      double oldDP = DP[i][0];
      if (DP[i][0] > 1e50 * DP[i+1][0])  oldDP /= 1e90;

      if (DP[i+1][0] > oldDP){
        res[i] = true;
        gold = false;
      }
    }
    else {
      double oldDP = DP[i][1];
      if (DP[i][1] > 1e50 * DP[i+1][1])  oldDP /= 1e90;

      if (DP[i+1][1] > DP[i][1]){
        res[i] = true;
        gold = true;
      }
    }
  }

    FOR(i,0,n){
      cout << res[i] << " ";
    } cout << endl;



}

提出情報

ジャッジ結果