PTA 1029 Median

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 const int maxn = 2e5 + 7;
 4 using namespace std;
 5 int a[maxn];
 6 int n,m;
 7 int main()
 8 {
 9     ios::sync_with_stdio(false);
10     cin.tie(0), cout.tie(0);
11     cin>>n;
12     for(int i = 1; i <= n ; i++) cin>>a[i];
13     a[n+1]=INF;
14     cin>>m;
15     int midpos = (n+m+1)>>1, temp, i = 1, flag = 0;
16     for(int j = 1; j <= m ; j++)
17     {
18         cin>>temp;
19         while(a[i] < temp)
20         {
21             flag++;
22             if(flag == midpos) cout<<a[i]<<endl;
23             i++;
24         }
25         flag++;
26         if(flag == midpos) cout<<temp<<endl;
27     }
28     while(i <= n)
29     {
30         flag++;
31         if(flag == midpos) cout<<a[i]<<endl;
32         i++;
33     }
34     return 0;
35 }