Submission #3782514
Source Code Expand
#include<bits/stdc++.h>
#define ff(i, x, y) for(int i = x;i <= y;i++)
using namespace std;
typedef long long ll;
int n, pre[100010], mes[100010], ans, bit[200010], cnt;
ll sum;
//map<int, int>mp;
int lowbit(int x)
{
return x&(-x);
}
void add(int i,int x)
{
while(i<=n + 100005)
{
bit[i]+=x;
i+=lowbit(i);
}
return;
}
void sub(int i,int x)
{
while(i<=n + 100005)
{
bit[i]-=x;
i+=lowbit(i);
}
return;
}
int qsum(int i)
{
int s=0;
while(i>0)
{
s+=bit[i];
i-=lowbit(i);
}
return s;
}
bool check(int x) {
ll tmp = 0;
ff(i, 1, n) {
if(mes[i] <= x)
pre[i] = -1;
else
pre[i] = 1;
pre[i] += pre[i - 1];
// bit[i] = bit[i + 100005] = 0;
}
ff(i, 1, 200005)
bit[i] = 0;
add(100005, 1);
ff(i, 1, n) {
tmp = tmp + i - qsum(pre[i] + 100005);
add(pre[i] + 100005, 1);
// cout << tmp << endl;
}
//cout << " " << x << " " << tmp << endl;
//cout << tmp << endl;
if(tmp >= sum / 2 + 1)
return true;
return false;
}
int main() {
scanf("%d", &n);
sum = (n + 1);
sum = sum * n / 2;
ff(i, 1, n) {
scanf("%d", &mes[i]);
//pre[i] = mes[i];
}
int l = 0, r = 1e9 + 7, mid = (l + r) / 2;
//cout << mid << endl;
while(l <= r) {
mid = (l + r) / 2;
if(check(mid)) {
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
printf("%d\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Median of Medians |
User |
Acnext |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
1469 Byte |
Status |
AC |
Exec Time |
102 ms |
Memory |
1792 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:65:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:69:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &mes[i]);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
700 / 700 |
Status |
|
|
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 |
4 ms |
1024 KB |
0_01.txt |
AC |
4 ms |
1024 KB |
0_02.txt |
AC |
4 ms |
1024 KB |
1_00.txt |
AC |
4 ms |
1024 KB |
1_01.txt |
AC |
4 ms |
1024 KB |
1_02.txt |
AC |
77 ms |
1792 KB |
1_03.txt |
AC |
79 ms |
1792 KB |
1_04.txt |
AC |
79 ms |
1792 KB |
1_05.txt |
AC |
78 ms |
1792 KB |
1_06.txt |
AC |
79 ms |
1792 KB |
1_07.txt |
AC |
78 ms |
1792 KB |
1_08.txt |
AC |
102 ms |
1792 KB |
1_09.txt |
AC |
102 ms |
1792 KB |
1_10.txt |
AC |
101 ms |
1792 KB |
1_11.txt |
AC |
101 ms |
1792 KB |
1_12.txt |
AC |
99 ms |
1792 KB |
1_13.txt |
AC |
102 ms |
1792 KB |
1_14.txt |
AC |
101 ms |
1792 KB |
1_15.txt |
AC |
101 ms |
1792 KB |