Submission #71014199

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;

int main () {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  vector<int64_t> a(n);
  for (auto& x: a) cin >> x;
  sort(a.begin(), a.end());
  vector<tuple<int64_t, int64_t, mint>> segs;
  segs.emplace_back(0, 0, 1);
  for (auto& x: a) {
    int sz = (int)segs.size();
    segs.reserve(2*sz);
    for (int i = 0; i < sz; i++) {
      auto [l, r, cnt] = segs[i];
      segs.emplace_back(l+x, r+x, cnt);
    }

    sort(segs.begin(), segs.end(), [&] (auto& A, auto& B) {
      return make_pair(get<0>(A), get<1>(A)) < make_pair(get<0>(B), get<1>(B));
    });

    sz = 0;
    for (int i = 0; i < (int)segs.size(); i++) {
      if (sz > 0 && 101*get<1>(segs[sz-1]) > 100*get<0>(segs[i])) {
        get<1>(segs[sz-1]) = max(get<1>(segs[sz-1]), get<1>(segs[i]));
        get<2>(segs[sz-1]) += get<2>(segs[i]);
      }
      else {
        segs[sz++] = segs[i];
      }
    }
    segs.resize(sz);
  }

  mint s = 0;
  cout << (int)segs.size()-1 << '\n';
  for (int i = 0; i+1 < (int)segs.size(); i++) {
    s += get<2>(segs[i]);
    cout << get<1>(segs[i]) << ' ' << get<0>(segs[i+1]) << ' ' << s.val() << '\n';
  }
}

Submission Info

Judge Result