2019-09-07 12:28:07 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> using namespace std; #define ALL(A) (A).begin(),(A).end() #define ll long long ll msize; ll count(vector<int> &c){ ll ret = 0; cout << "c.size() = " << c.size() << endl; for(auto x:c) cout << x << " "; for(int i=1;i<c.size();i++){ for(int j=i;j<=c.size();j++){ if(c[j]-c[i-1]>=0)ret++; } } cout << " ret= " << ret << endl; return ret; } bool check(vector<int> &a,int k){ vector<int> b = a,c(a.size()+1); for(int i=0;i<b.size();i++){ if(b[i] >= k)b[i]=1; else b[i] = -1; } c[0] = 0; for(int i=0;i<b.size();i++){ c[i+1] = c[i] + b[i]; } //cのある区間について、k以上の数をカウントする if(count(c) >= (msize+1)/2)return 1; else return 0; } int main(void){ int N,Max=0; cin >> N; vector<int> a(N); msize = N*(N+1)/2; for(int i=0;i<N;i++){ cin >> a[i]; Max = max(Max,a[i]); } int ok = 0; int ng = Max+1; while(abs(ok-ng)>1){ int mid = (ok+ng)/2; //check(vector<int> &a,mid)はmid以上の数がmに半分以上含まれていた場合1を返す if(check(a,mid)){ ok = mid; }else{ ng = mid; } } cout << ok << endl; }
RECOMMEND