QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #827988 | #9914. 前往何方 | Hanghang | 0 | 0ms | 0kb | C++20 | 847b | 2024-12-23 12:05:19 | 2024-12-23 12:05:21 |
answer
#include"wheretoreach.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1e5+3;
int d[N];
void Sol(vector<int> &a)
{
int n=(int)a.size();
if(n==2){report(a[0],a[1]);return;}
int rt=0,rtsz=n;
for(int x:a)
{
d[x]=remove(x),add(x);
if(d[x]<rtsz)rtsz=d[x],rt=x;
}
vector<array<int,2>>b;
for(int x:a)if(x!=rt)b.pb({n-d[x],x});
sort(b.begin(),b.end(),greater<>());
int now=n,fl=0;
vector<int>QA,QB;QA.pb(rt);QB.pb(rt);
for(auto [v,id]:b)
{
if(!fl)
{
now=remove(id);QA.pb(id);
if(now<=(n+1)/2)fl=1;
}
else
{
int tmp=remove(id);
if(tmp<now)add(id),QB.pb(id);
else QA.pb(id);
}
}
Sol(QB);
for(int id:QB)remove(id);
for(int id:QA)add(id);
Sol(QA);
}
void solve(int n)
{
vector<int>a;
for(int i=1;i<=n;i++)add(i),a.pb(i);
Sol(a);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Memory Limit Exceeded
Test #1:
score: 0
Memory Limit Exceeded
input:
500 310 77 468 235 218 93 58 406 223 334 159 243 204 48 144 107 492 288 447 165 102 407 340 299 450 126 140 234 209 62 111 204 453 306 4 476 126 358 183 317 360 489 149 158 232 22 326 372 92 383 410 24 199 14 401 480 69 329 192 167 409 152 426 354 435 60 146 404 334 187 208 305 123 55 30 79 469 72 2...
output:
Unauthorized output
result:
Subtask #2:
score: 0
Memory Limit Exceeded
Test #9:
score: 0
Memory Limit Exceeded
input:
2500 887 818 1296 878 1605 2107 803 2410 1919 1135 860 1160 1364 2414 1375 500 894 2173 2322 2449 211 1732 1821 573 413 1556 1574 1977 709 162 2002 1577 1626 1895 1563 688 2151 2293 661 69 317 1170 2335 1549 1481 1349 1500 779 1593 735 1824 2380 639 2334 1496 2335 1956 1384 2476 1583 1035 163 720 70...
output:
Unauthorized output
result:
Subtask #3:
score: 0
Memory Limit Exceeded
Test #17:
score: 0
Memory Limit Exceeded
input:
10000 6139 8917 131 5800 5366 5247 1298 5035 3966 3518 4889 7202 6547 1919 5829 9494 8012 6029 3868 6403 1909 8116 5734 6122 2683 4779 9275 6673 7433 9042 7646 2032 3547 6306 1943 8382 4061 6428 8240 3548 460 2795 3451 4320 5904 6627 8709 7621 8706 3534 748 4873 8101 4261 5359 3304 6254 4687 6492 53...
output:
Unauthorized output