結果
問題 | No.275 中央値を求めよ |
ユーザー |
![]() |
提出日時 | 2021-11-24 21:05:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 12,388 bytes |
コンパイル時間 | 4,256 ms |
コンパイル使用メモリ | 243,960 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-27 06:55:25 |
合計ジャッジ時間 | 5,550 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;//#pragma GCC target ("avx2")//#pragma GCC optimization("O3")//#pragma GCC optimization("unroll-loops")//#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#define int long long#define double long double#define stoi stoll#define endl "\n"using std::abs;using namespace std;//constexpr int MOD = 1000000007;constexpr int MOD = 998244353;constexpr double PI = 3.14159265358979323846;const int INF = 1LL << 60;const int dx[4] = { 0, 1, 0, -1 };const int dy[4] = { -1, 0, 1, 0 };#define rep(i,n) for(int i=0;i<n;++i)#define REP(i,n) for(int i=1;i<=n;i++)#define krep(i,k,n) for(int i=(k);i<n+k;i++)#define Krep(i,k,n) for(int i=(k);i<n;i++)#define rrep(i,n) for(int i=n-1;i>=0;i--)#define Rrep(i,n) for(int i=n;i>0;i--)#define LAST(x) x[x.size()-1]#define ALL(x) (x).begin(),(x).end()#define MAX(x) *max_element(ALL(x))#define MIN(x) *min_element(ALL(x)#define RUD(a,b) (((a)+(b)-1)/(b))#define sum1_n(n) ((n)*(n+1)/2)#define SUM1n2(n) (n*(2*n+1)*(n+1))/6#define SUMkn(k,n) (SUM1n(n)-SUM1n(k-1))#define SZ(x) ((int)(x).size())#define PB push_back#define Fi first#define Se secondtypedef vector<int> vint;typedef vector<vint> vvint;typedef vector<vvint> vvvint;typedef vector<double> vdouble;typedef vector<vdouble> vvdouble;typedef vector<vvdouble> vvvdouble;typedef vector<string> vstring;typedef vector<bool> vbool;typedef vector<vbool> vvbool;typedef vector<vvbool> vvvbool;typedef map<int, int> mapint;typedef pair<int, int> pint;typedef pair<string, string> pstring;typedef pair<vstring,vstring> pvstring;typedef tuple<int, int, int>tint;typedef vector<pint> vpint;typedef vector<vpint> vvpint;typedef vector<tint> vtint;typedef vector<vtint> vvtint;int factorial(int a) {if (a == 0)return 1;elsereturn a * factorial(a - 1);}int nPr(int n, int r) {int s = n - r + 1;int sum = 1;for (int i = s; i <= n; i++)sum *= i;return sum;}int GCD(int a, int b) {if (b == 0) return a;return GCD(b, a % b);}int LCM(int a, int b) {return a / GCD(a, b) * b;}double LOG(int a, int b) {return log(b) / log(a);}double DISTANCE(int x1, int y1, int x2, int y2) {return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));}inline bool BETWEEN(int x, int min, int max) {if (min <= x && x <= max)return true;elsereturn false;}inline bool between(int x, int min, int max) {if (min < x && x < max) return true;else return false;}inline bool BETWEEN2(int i,int j,int H,int W) {if (BETWEEN(i,0,H-1)&&BETWEEN(j,0,W-1)) return true;else return false;}template<class T>inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}template<class T>inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}inline bool bit(int x, int i) {return x >> i & 1;}int in() { int x; cin >> x; return x; }string ins() { string x; cin >> x; return x; }vint invi(int N) {vint x(N);rep(i, N)cin >> x[i];return x;}#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endltemplate<typename T,typename U>struct my_pair :std::pair<T,U>{using std::pair<T,U>::pair;my_pair<T,U> operator+(const my_pair<T,U> p){return my_pair<T,U>(this->first + p.first, this->second + p.second);}my_pair<T, U> operator-(const my_pair<T, U> p) {return my_pair<T, U>(this->first - p.first, this->second - p.second);}void print(){cout << this->first << " " << this->second << endl;}};template<int MOD> struct Fp {long long val;constexpr Fp(long long v = 0) noexcept : val(v% MOD) {if (val < 0) val += MOD;}constexpr int getmod() const { return MOD; }constexpr Fp operator - () const noexcept {return val ? MOD - val : 0;}constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }constexpr Fp& operator += (const Fp& r) noexcept {val += r.val;if (val >= MOD) val -= MOD;return *this;}constexpr Fp& operator -= (const Fp& r) noexcept {val -= r.val;if (val < 0) val += MOD;return *this;}constexpr Fp& operator *= (const Fp& r) noexcept {val = val * r.val % MOD;return *this;}constexpr Fp& operator /= (const Fp& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}constexpr bool operator == (const Fp& r) const noexcept {return this->val == r.val;}constexpr bool operator != (const Fp& r) const noexcept {return this->val != r.val;}friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {is >> x.val;x.val %= MOD;if (x.val < 0) x.val += MOD;return is;}friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {return os << x.val;}friend constexpr Fp<MOD> modpow(const Fp<MOD>& r, long long n) noexcept {if (n == 0) return 1;if (n < 0) return modpow(modinv(r), -n);auto t = modpow(r, n / 2);t = t * t;if (n & 1) t = t * r;return t;}friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}return Fp<MOD>(u);}};using mint = Fp<MOD>;const int MAXR = 110000;int fac[MAXR], finv[MAXR], inv[MAXR];void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAXR; i++) {fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}int nCr(int n, int k) {if (n < k)return 0;if (n < 0 || k < 0)return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}mint nCrm(long long N, long long K) {mint res = 1;if (N < K)return 0;if (N < 0 || K < 0)return 0;for (long long n = 0; n < K; ++n) {res *= (N - n);res /= (n + 1);}return res;}int nCr2(int n, int k) {//MODらない奴if (n < k)return 0;if (n < 0 || k < 0)return 1;int ans = 1;REP(i, k) {ans *= n--;ans /= i;}return ans;}vpint prime_factorize(int N) {vpint res;for (int i = 2; i * i <= N; i++) {if (N % i != 0)continue;int ex = 0;while (N % i == 0) {++ex;N /= i;}res.push_back({ i, ex });}if (N != 1)res.push_back({ N, 1 });return res;}double median(vint a) {sort(ALL(a));int N = a.size();if (N % 2 == 1)return (double)a[N / 2];elsereturn (double)(a[N / 2 - 1] + a[N / 2]) / 2;}typedef vector<mint> vmint;typedef vector<vmint> vvmint;int ipow(int x, int n) {int ans = 1;while (n > 0) {if (n & 1) ans *= x;x *= x;n >>= 1;}return ans;}string base_to_k(int n, int k) {//n(10)→n(k)string ans = "";while (n) {ans += to_string(n % k);n /= k;}reverse(ALL(ans));return ans;}string base(string n, int k, int l) {//n(k)→n(l)return n;}int mpow(int x, int n, int M) {int ans = 1;while (n > 0) {if (n & 1) ans = ans * x % M;x = x * x % M;n >>= 1;}return ans%M;}string base_from_k(string n, int k) {//n(k)→n(10)int ans = 0;int N = n.size();rep(i, N)ans += (n[N - 1 - i] - '0') * ipow(k, i);return to_string(ans);}template <typename T>vector<T> compress(vector<T>& X) {vector<T> vals = X;sort(ALL(vals));vals.erase(unique(ALL(vals)), vals.end());rep(i,SZ(X))X[i] = lower_bound(ALL(vals), X[i]) - vals.begin();return vals;}typedef complex<double> con;template< typename G >struct LowLink {const G& g;vector< int > used, ord, low;vector< int > articulation;vector< pair< int, int > > bridge;LowLink(const G& g) : g(g) {}int dfs(int idx, int k, int par) {used[idx] = true;ord[idx] = k++;low[idx] = ord[idx];bool is_articulation = false;int cnt = 0;for (auto& to : g[idx]) {if (!used[to]) {++cnt;k = dfs(to, k, idx);low[idx] = min(low[idx], low[to]);is_articulation |= ~par && low[to] >= ord[idx];if (ord[idx] < low[to]) bridge.emplace_back(minmax(idx, (int)to));}else if (to != par) {low[idx] = min(low[idx], ord[to]);}}is_articulation |= par == -1 && cnt > 1;if (is_articulation) articulation.push_back(idx);return k;}virtual void build() {used.assign(g.size(), 0);ord.assign(g.size(), 0);low.assign(g.size(), 0);int k = 0;for (int i = 0; i < g.size(); i++) {if (!used[i]) k = dfs(i, k, -1);}}};int LIS_op(int fi,int se) {return max(fi,se);}int LIS_e() {return 0;}struct LIS {int N=0, ans=0;vpint a;vint v;LIS(int n,vint x) {N = n;a.resize(N);v.resize(N);rep(i, N)a[i] = { x[i],i };sort(ALL(a));}int solve() {segtree<int, LIS_op, LIS_e> seg(v);rep(i, N) {int m = seg.prod(0, a[i].second) + 1;seg.set(a[i].second, m);chmax(ans, m);}return ans;}};class LCA {private:int root;int k; // n<=2^kとなる最小のkvector<vector<int>> dp; // dp[i][j]:=要素jの2^i上の要素vector<int> depth; // depth[i]:=rootに対する頂点iの深さpublic:LCA(const vector<vector<int>>& _G, const int _root = 0) {int n = _G.size();root = _root;k = 1;int nibeki = 2;while (nibeki < n) {nibeki <<= 1;k++;}// 頂点iの親ノードを初期化dp = vector<vector<int>>(k + 1, vector<int>(n, -1));depth.resize(n);function<void(int, int)> _dfs = [&](int v, int p) {dp[0][v] = p;for (auto nv : _G[v]) {if (nv == p) continue;depth[nv] = depth[v] + 1;_dfs(nv, v);}};_dfs(root, -1);// ダブリングfor (int i = 0; i < k; i++) {for (int j = 0; j < n; j++) {if (dp[i][j] == -1) continue;dp[i + 1][j] = dp[i][dp[i][j]];}}}/// get LCAint get(int u, int v) {if (depth[u] < depth[v]) swap(u, v); // u側を深くするif (depth[u] != depth[v]) {long long d = depth[u] - depth[v];for (int i = 0; i < k; i++) if ((d >> i) & 1) u = dp[i][u];}if (u == v) return u;for (int i = k; i >= 0; i--) {if (dp[i][u] != dp[i][v]) {u = dp[i][u], v = dp[i][v];}}return dp[0][u];}int get_distance(const int u, const int v) {int lca = get(u, v);return depth[u] + depth[v] - 2 * depth[lca];}};mint res = 0;template<typename T> class BIT {private:int n;vector<T> bit;public:// 0_indexed で i 番目の要素に x を加えるvoid add(int i, T x) {i++;while (i < n) {bit[i] += x, i += i & -i;}}// 0_indexed で [0,i] の要素の和(両閉区間!!)T sum(int i) {i++;T s = 0;while (i > 0) {s += bit[i], i -= i & -i;}return s;}BIT() {}//初期値がすべて0の場合BIT(int sz) : n(sz + 1), bit(n, 0) {}BIT(const vector<T>& v) : n((int)v.size() + 1), bit(n, 0) {for (int i = 0; i < n - 1; i++) {add(i, v[i]);}}void print() {for (int i = 0; i < n - 1; i++) {cout << sum(i) - sum(i - 1) << " ";}cout << "\n";}//-1スタートvoid print_sum() {for (int i = 0; i < n; i++) {cout << sum(i - 1) << " ";}cout << "\n";}};// u を昇順にソートするのに必要な交換回数(転倒数) (u は {0,..., n-1} からなる重複を許した長さ n の数列)long long inv_count(const vector<int>& u){int n = (int)u.size();BIT<int> bt(n);long long ans = 0;for (int i = 0; i < n; i++) {ans += i - bt.sum(u[i]);int x = i - bt.sum(u[i]);res += mpow(2, n-1 -(x+u[i]), MOD) - 1;cout << x<<" "<<u[i] << endl;bt.add(u[i], 1);}return ans;}void solve() {int N = in();vint a(N);rep(i, N)cin >> a[i];cout << median(a) << endl;}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout << fixed << setprecision(15);solve();}//bit全探索/*rep(i,1LL<<N){rep(j,N){if (bit(i,j)){}}}*///素因数分解/*const auto& res = prime_factorize(N);for (auto p : res) {}*/