Submission #3104979


Source Code Expand

Copy
#include <bits/stdc++.h>
#define pb push_back
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
#define MOD 998244353
#define bitcnt(a) (ll) __builtin_popcount((a))
#define lb(a, b) lower_bound((a).begin(), (a).end(), (b))
#define ub(a, b) upper_bound((a).begin(), (a).end(), (b))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<string, string> PS;

template <class T>
struct BIT {
  vector<T> x;
  BIT(int n) : x(n, 0) {
    // initialize
  }

  T sum(int i, int j) {
    if (i == 0) {
      T S = 0;
      for (j; j >= 0; j = (j & (j + 1)) - 1)
        S += x[j];
      return S;
    } else
      return sum(0, j) - sum(0, i - 1);
  }
  void add(int k, T a) {

    for (; k < x.size(); k |= k + 1)
      x[k] += a;
  }
};

int main() {
  ll n;
  cin >> n;
  vector<ll> v;
  REP(i, n) {
    ll h;
    cin >> h;
    v.pb(h);
  }
  vector<ll> s = v;

  sort(s.begin(), s.end());
  s.erase(unique(s.begin(), s.end()), s.end());

  ll ok = 0, ng = s.size();

  while (ng - ok > 1) {
    ll m = s[(ok + ng) / 2];
    vector<ll> imos;
    for (auto &a : v) {
      if (a < m) {
        imos.pb(-1);
      } else {
        imos.pb(1);
      }
    }

    REP(i, imos.size() - 1) {
      imos[i + 1] += imos[i];
    }
    BIT<ll> b(2 * n + 1);

    ll cnt = 0;
    REP(i, n) {
      cnt += (i - b.sum(0, imos[i] + n)) + (imos[i] < 0);
      //自分より小さい中央値のものを足す
      b.add(imos[i] + n, 1);
    }
    if (cnt <= (n + (n * (n - 1)) / 2) / 2) {
      //cout << cnt << " " << m << endl;
      ok = (ok + ng) / 2;
    } else {
      //cout << cnt << " " << m << endl;
      ng = (ok + ng) / 2;
    }
  }
  cout << s[ok] << endl;
}

Submission Info

Submission Time
Task D - Median of Medians
User keidaroo
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1773 Byte
Status
Exec Time 118 ms
Memory 5240 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_00.txt, 0_01.txt, 0_02.txt
All 700 / 700 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt
Case Name Status Exec Time Memory
0_00.txt 1 ms 256 KB
0_01.txt 1 ms 256 KB
0_02.txt 1 ms 256 KB
1_00.txt 1 ms 256 KB
1_01.txt 1 ms 256 KB
1_02.txt 19 ms 1908 KB
1_03.txt 46 ms 1908 KB
1_04.txt 87 ms 5240 KB
1_05.txt 86 ms 5240 KB
1_06.txt 88 ms 5240 KB
1_07.txt 91 ms 5240 KB
1_08.txt 117 ms 5176 KB
1_09.txt 117 ms 5196 KB
1_10.txt 116 ms 5108 KB
1_11.txt 116 ms 5108 KB
1_12.txt 113 ms 5080 KB
1_13.txt 118 ms 5224 KB
1_14.txt 113 ms 5176 KB
1_15.txt 114 ms 5212 KB