Contest Duration: - (local time) (100 minutes) Back to Home

Submission #3098603

Source Code Expand

Copy
```#include <iostream>
#include<algorithm>
#include <vector>
#include<cmath>
using namespace std;

int N;
int bit[1000010];
void init(int size){

for(int i = 0; i < size; i++)
{
bit[i] = 0;
}

}
void add(int a, int w) {
for (int x = a; x <= 1000010; x += x & -x) bit[x] += w;
}
int sum(int a) {
int ret = 0;
for (int x = a; x > 0; x -= x & -x) ret += bit[x];
return ret;
}

int main()
{
int N;
cin >> N;

vector<int> A(N);
vector<int> sorted(N);
for (int i = 0; i < N; i++)
{
cin >> A[i];
sorted[i] = A[i];
}
sort(sorted.begin(), sorted.end());

vector<int> S(N);

int lb =0, ub = N;
while(ub - lb > 1){
// cout << "ub=" << ub <<"lb=" << lb << endl;

init(2*N+1);
// cout << "------" << endl;
int len = ub-lb;
int x = len/2;
int median = sorted[x+lb];
// cout << "median:" << median << endl;
for (int i = 0; i < N; i++)
{
if (median <= A[i])
{
S[i] = 1;
}
else
{
S[i] = -1;
}
}
for (int i = 0; i < N; i++)
{
if (i != 0)
{
S[i] = S[i - 1] + S[i];
}
else
{
S[0] = S[0];
}
}

int cnt = 0;
for(int i = 0; i < N; i++)
{
cnt += sum(S[i]+N);
// cout << "sum("<<S[i]+N<<")="<<sum(S[i]+N)<<endl;

}
// cout << "cnt=" << cnt << endl;
if(cnt>=ceil(N*(N+1)/2/2)){
lb = x+1;
}else{
ub = x-1;
}
// break;
}
cout << sorted[lb] << endl;
return 0;
}
```

Submission Info

Submission Time 2018-08-29 20:24:37+0900 D - Median of Medians yusan1871 C++14 (GCC 5.4.1) 0 1496 Byte WA 2103 ms 2176 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
 AC × 3
 AC × 5 WA × 4 TLE × 10
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt
All 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 AC 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 1 ms 256 KB
1_02.txt TLE 2103 ms 2176 KB
1_03.txt TLE 2103 ms 2176 KB
1_04.txt TLE 2103 ms 2176 KB
1_05.txt TLE 2103 ms 2176 KB
1_06.txt WA 46 ms 2176 KB
1_07.txt WA 43 ms 2176 KB
1_08.txt TLE 2103 ms 2176 KB
1_09.txt TLE 2103 ms 2176 KB
1_10.txt WA 53 ms 2176 KB
1_11.txt TLE 2103 ms 2176 KB
1_12.txt WA 52 ms 2176 KB
1_13.txt TLE 2103 ms 2176 KB
1_14.txt TLE 2103 ms 2176 KB
1_15.txt TLE 2103 ms 2176 KB