Person in Charge

• 035966_L3

Attention

Please strictly follow the submission instructions.

The memory limit for this problem is 8 MB.

Problem Description

Given $n$ positive integers (guaranteed to be an odd count), find their median.

Submission Method

Use the following template. Your program will read two positive integers $n, x$ (guaranteed that $n$ is odd) and then call the get() function $n$ times to obtain the $n$ positive integers (each guaranteed to be no larger than $2^{32}-1$). After obtaining all $n$ integers, output their median.

#include <bits/stdc++.h>
using namespace std;
unsigned int n, x;
inline unsigned int get()
{
    x ^= x << 7;
    x ^= x >> 23;
    x ^= x << 12;
	return x;
}
int main()
{
    freopen("median.in", "r", stdin);
    freopen("median.out", "w", stdout);
    cin >> n >> x;
    unsigned int answer = 0;
    // Call the function 'get()' to get the integers.
    // You should call the function 'get()' exactly N times.
    // An integer will be given after each call.
    cout << answer << endl;
    return 0;
}

Samples

1 3489531249

4213554576

3 3489531249

3736028483

5 3489531249

1591798959

7 3489531249

1591798959

9 3489531249

1591798959

Sample Explanation

The first $9$ values returned by get() are:

4213554576
3736028483
1464923601
1591798959
1159830386
399619033
2061643431
1546026288
3242329518

Data Range

• For $50\%$ of the data, $1 \le n \le 10^5+1$.
• For $100\%$ of the data, $1 \le n \le 10^8+1$，$1 \le x \le 2^{32}-1$.

Official Solution

link