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];
			}
		}
		
		// add(N,1);
		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;
			add(S[i]+N,1);

		}
		// 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
Task D - Median of Medians
User yusan1871
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1496 Byte
Status WA
Exec Time 2103 ms
Memory 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