NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #208306 | #3760. 中位数 | huangyuhang | 100 | 1705ms | 9232kb | C++11 | 800b | 2024-08-02 09:50:58 | 2024-08-02 12:09:52 |
answer
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int main()
{
// freopen("中位数.in","r",stdin);
// freopen("中位数.out","w",stdout);
int n,num1,num2;
scanf("%d",&n);
scanf("%d",&num1);
printf("%d\n",num1);
int mid=num1;
priority_queue<int,vector<int>,greater<int>>Q2;//小根堆
priority_queue<int,vector<int>,less<int>>Q1;//大根堆
for(int i=3;i<=n;i+=2)
{
scanf("%d",&num1);
scanf("%d",&num2);
if(num1>mid)
Q2.push(num1);
else
Q1.push(num1);
if(num2>mid)
Q2.push(num2);
else
Q1.push(num2);
while(Q1.size()>Q2.size())
{
Q2.push(mid);
mid=Q1.top();
Q1.pop();
}
while(Q1.size()<Q2.size())
{
Q1.push(mid);
mid=Q2.top();
Q2.pop();
}
printf("%d\n",mid);
}
return 0;
}
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1252kb
input:
999 500000349 500000416 500000169 500000400 500000251 500000501 500000004 500000484 500000326 500000...
output:
500000349 500000349 500000349 500000349 500000349 500000326 500000281 500000251 500000278 500000251 ...
result:
ok 500 lines
Test #2:
score: 10
Accepted
time: 1ms
memory: 1252kb
input:
999 500000222 500000210 500000343 500000339 500000232 500000115 500000462 500000269 500000231 500000...
output:
500000222 500000222 500000232 500000232 500000232 500000232 500000232 500000232 500000232 500000231 ...
result:
ok 500 lines
Test #3:
score: 10
Accepted
time: 0ms
memory: 1248kb
input:
999 500000312 500000111 500000373 500000171 500000011 500000135 500000130 500000148 500000284 500000...
output:
500000312 500000312 500000171 500000135 500000148 500000171 500000171 500000171 500000200 500000200 ...
result:
ok 500 lines
Test #4:
score: 10
Accepted
time: 0ms
memory: 1248kb
input:
999 500000244 500000352 500000490 500000386 500000026 500000381 500000010 500000267 500000265 500000...
output:
500000244 500000352 500000352 500000352 500000267 500000267 500000265 500000265 500000267 500000267 ...
result:
ok 500 lines
Test #5:
score: 10
Accepted
time: 13ms
memory: 1612kb
input:
99999 500054267 500035412 500041365 500038761 500034334 500015071 500020907 500007213 500058496 5000...
output:
500054267 500041365 500038761 500035412 500035412 500034334 500030136 500023452 500030136 500034334 ...
result:
ok 50000 lines
Test #6:
score: 10
Accepted
time: 19ms
memory: 1628kb
input:
99999 500006290 500034296 500017269 500004468 500009242 500018632 500056010 500055653 500026987 5000...
output:
500006290 500017269 500009242 500017269 500018632 500018632 500018632 500018632 500026987 500018632 ...
result:
ok 50000 lines
Test #7:
score: 10
Accepted
time: 21ms
memory: 1608kb
input:
99999 500034174 500012905 500059611 500030852 500006349 500056601 500040197 500050573 500048073 5000...
output:
500034174 500034174 500030852 500034174 500040197 500034174 500030852 500020997 500030843 500030843 ...
result:
ok 50000 lines
Test #8:
score: 10
Accepted
time: 455ms
memory: 9140kb
input:
1999999 501757318 500661812 501838931 501096674 501347961 500244154 500892159 501858821 500964235 50...
output:
501757318 501757318 501347961 501096674 501096674 501096674 501096674 501038815 501038815 501002394 ...
result:
ok 1000000 lines
Test #9:
score: 10
Accepted
time: 736ms
memory: 9140kb
input:
1999999 501485921 501744371 501128867 500751126 501658197 501136617 500406037 500448369 500746821 50...
output:
501485921 501485921 501485921 501136617 501128867 501128867 501136617 501128867 501119509 501128867 ...
result:
ok 1000000 lines
Test #10:
score: 10
Accepted
time: 460ms
memory: 9232kb
input:
1999999 501679123 501742012 501806641 500774076 501854402 501571146 501073353 500345154 500367723 50...
output:
501679123 501742012 501742012 501679123 501571146 501073353 501073353 501057056 501057056 501057056 ...
result:
ok 1000000 lines
Extra Test:
score: 0
Extra Test Passed
