QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#794861 | #9556. The Hanged Man | Nightsky | AC ✓ | 273ms | 80888kb | C++20 | 2.6kb | 2024-11-30 16:31:21 | 2024-11-30 16:31:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
vector<int> e[MAXN];
int n,d[MAXN],dep[MAXN],llf,num,exlf;
int dfn[MAXN],totdfn,st[MAXN][20],lg[MAXN];
bool del[MAXN];
struct edge
{
int u,v;
};
vector <edge> res;
int Get(int x,int y)
{
if(dfn[x] < dfn[y]) return x;
else return y;
}
void build()
{
for(int j = 1;j <= lg[n]; ++j)
for(int i = 1; i + (1 << j) - 1 <=n; ++i)
st[i][j] = Get(st[i][j - 1],st[i + (1 << j - 1)][j - 1]);
}
int lca(int u,int v)
{
if(u == v) return u;
if(dfn[u] > dfn[v]) swap(u,v);
int k = lg[dfn[v] - dfn[u]];
return Get(st[dfn[u] + 1][k],st[dfn[v] - (1 << k) + 1][k]);
}
void dfs(int p,int fa)
{
dfn[p] = ++totdfn;st[totdfn][0] = fa;
for(int v : e[p])
{
if(v == fa) continue;
dfs(v,p);
}
int lst = 0;
for(int v : e[p])
{
if(v == fa) continue;
if(d[v] == 1)
{
if(lst)
{
res.push_back({lst,v});
num -= 2;d[p] -= 2;
del[lst] = del[v] = 1;
lst = 0;
}
else lst = v;
}
}
}
void solve(int p,int fa)
{
if(d[p] == 1 && p != 1)
{
int LCA = lca(llf,p);
if(exlf) LCA = exlf,exlf = 0;
res.push_back({LCA,p});
llf = p;
}
sort(e[p].begin(),e[p].end(),[&](int x,int y){return d[x] < d[y];});
// cout<<"solve p:"<<p<<endl;
for(int v : e[p])
{
if(v == fa || del[v]) continue;
solve(v,p);
}
}
int main()
{
for(int i = 2; i <= 300000; ++i) lg[i] = lg[i >> 1] + 1;
int T;scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i = 1; i <= n; ++i)
{
e[i].clear();
d[i] = 0;del[i] = 0;
}
num = n;llf = 1;totdfn = 0;exlf = 0;
res.clear();
for(int i = 1; i < n; ++i)
{
int u,v;scanf("%d %d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
d[u]++;d[v]++;
}
dfs(1,0);
build();
for(int v : e[1])
if(!del[v] && d[v] == 1) exlf = v,del[v] = 1;
// cout<<"size:"<<endl;
// cout << res.size()<<endl;
solve(1,0);
if(num == 2) printf("-1\n");
else
{
int k = res.size();
printf("%d\n",k);
for(auto [u,v] : res)
printf("%d %d\n",u,v);
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9096kb
input:
3 4 1 2 2 3 2 4 7 1 2 1 3 1 4 4 5 4 6 4 7 6 1 2 2 3 2 4 1 5 5 6
output:
-1 3 5 6 2 3 1 7 2 3 4 2 6
result:
ok Good Job! (3 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 9972kb
input:
3 6 1 2 1 3 1 4 4 5 4 6 2 1 2 2 2 1
output:
-1 -1 -1
result:
ok Good Job! (3 test cases)
Test #3:
score: 0
Accepted
time: 39ms
memory: 9236kb
input:
100000 3 1 3 2 1 3 2 3 1 2 3 2 3 1 3 3 2 1 1 3 3 1 2 2 3 3 1 3 2 3 3 2 1 1 3 3 2 3 1 2 3 2 3 1 3 3 2 1 1 3 3 2 3 1 2 3 1 3 2 3 3 1 3 2 1 3 2 3 1 2 3 2 3 1 3 3 1 3 2 1 3 1 2 2 3 3 1 3 2 3 3 2 1 1 3 3 1 2 2 3 3 1 3 2 3 3 1 3 2 1 3 2 3 1 2 3 1 3 2 3 3 1 3 2 1 3 2 3 1 2 3 1 3 2 3 3 2 1 1 3 3 2 3 1 2 3 2...
output:
1 3 2 1 1 3 1 1 2 1 2 3 1 1 3 1 1 2 1 2 3 1 1 3 1 1 2 1 2 3 1 1 3 1 1 2 1 3 2 1 1 3 1 1 2 1 3 2 1 1 3 1 1 2 1 2 3 1 1 3 1 1 2 1 3 2 1 1 3 1 1 2 1 3 2 1 1 3 1 1 2 1 2 3 1 1 3 1 1 2 1 3 2 1 1 3 1 1 2 1 3 2 1 1 3 1 1 2 1 2 3 1 1 3 1 1 2 1 3 2 1 1 3 1 1 2 1 2 3 1 1 3 1 1 2 1 2 3 1 1 3 1 1 2 1 3 2 1 1 3 ...
result:
ok Good Job! (100000 test cases)
Test #4:
score: 0
Accepted
time: 36ms
memory: 9056kb
input:
75000 4 3 1 2 1 1 4 4 3 1 2 4 1 2 4 2 1 1 3 3 4 4 1 4 2 1 3 4 4 2 1 3 2 1 4 4 3 2 2 4 1 2 4 2 3 3 4 1 2 4 3 4 2 4 1 2 4 3 1 1 4 2 3 4 3 2 1 3 2 4 4 2 3 1 3 3 4 4 1 3 3 4 2 4 4 3 1 1 4 2 4 4 3 2 2 4 1 4 4 2 3 3 4 1 4 4 3 4 2 4 1 4 4 1 4 2 1 3 1 4 2 4 3 1 1 2 4 2 1 3 4 1 3 4 2 1 1 4 3 4 4 1 4 2 1 3 2 ...
output:
-1 1 3 4 1 2 4 1 2 3 1 4 3 -1 1 1 4 1 1 3 1 4 2 1 1 4 -1 1 1 2 1 3 2 1 1 3 1 1 2 -1 -1 1 3 4 1 2 4 1 2 3 1 4 3 -1 1 1 4 1 1 3 1 4 2 1 1 4 -1 1 1 2 1 3 2 1 1 3 1 1 2 -1 -1 1 3 4 1 2 4 1 2 3 1 4 3 -1 1 1 4 1 1 3 1 4 2 1 1 4 -1 1 1 2 1 3 2 1 1 3 1 1 2 -1 -1 1 3 4 1 2 4 1 2 3 1 4 3 -1 1 1 4 1 1 3 1 4 2 ...
result:
ok Good Job! (75000 test cases)
Test #5:
score: 0
Accepted
time: 40ms
memory: 12200kb
input:
60000 5 2 1 3 1 4 1 1 5 5 1 2 4 1 2 5 3 1 5 1 3 3 5 4 1 2 1 5 2 1 4 5 1 4 3 1 5 3 1 1 5 2 1 4 5 5 3 1 4 2 1 5 2 1 5 1 2 3 1 2 5 4 2 5 4 1 1 2 3 5 2 3 5 3 1 2 4 4 5 1 2 5 4 5 3 1 2 5 1 2 5 1 5 2 1 3 1 4 3 5 1 3 4 1 2 5 3 2 5 4 3 2 1 1 3 3 5 5 3 4 1 3 4 5 2 1 5 2 1 1 3 4 5 3 5 5 3 4 4 1 1 5 2 1 5 3 1 ...
output:
2 2 3 4 5 2 4 3 1 5 2 4 2 1 5 2 2 3 1 5 2 3 2 1 4 2 3 5 1 4 2 5 4 2 3 1 4 5 1 3 5 1 3 4 2 5 2 1 4 1 4 5 2 4 5 2 3 1 2 5 1 2 4 2 5 2 1 3 1 3 5 1 2 5 2 5 3 4 2 1 2 3 2 2 4 1 3 1 3 4 1 2 4 1 2 3 2 4 3 2 5 2 5 4 1 3 2 3 5 2 4 2 1 5 1 4 2 1 5 1 3 2 1 3 1 4 2 3 4 5 2 2 5 4 1 3 2 1 4 2 5 2 1 3 2 5 2 1 3 2 ...
result:
ok Good Job! (60000 test cases)
Test #6:
score: 0
Accepted
time: 34ms
memory: 9168kb
input:
50000 6 1 6 5 1 4 1 2 1 3 1 6 5 1 3 1 1 2 2 6 4 1 6 4 1 5 1 1 3 2 1 3 6 6 4 6 2 1 5 1 3 1 1 4 6 5 6 1 5 4 1 3 1 2 1 6 4 1 5 6 2 1 1 6 3 1 6 1 6 3 1 2 1 5 2 4 1 6 3 1 5 2 1 2 2 6 4 1 6 4 1 2 3 5 1 1 2 3 6 6 4 6 1 2 3 1 2 4 5 1 6 1 2 5 6 2 5 3 1 4 1 6 1 2 2 6 4 1 3 1 5 6 6 5 3 3 1 1 6 2 1 4 1 6 5 1 3 ...
output:
-1 2 5 3 4 6 2 4 5 2 6 2 2 5 3 6 2 4 3 2 6 2 4 2 3 5 2 6 3 4 5 -1 2 4 5 1 6 2 3 5 1 6 2 3 4 1 6 2 4 3 1 5 2 6 2 4 5 2 5 4 1 6 -1 2 2 5 1 6 2 2 4 1 6 2 4 2 1 5 2 3 6 2 5 2 3 5 1 6 2 2 5 1 6 -1 2 2 3 1 6 2 2 3 1 5 2 3 2 6 4 2 3 4 1 6 2 4 2 1 6 2 2 3 1 6 -1 2 3 2 1 4 2 3 5 2 4 2 4 3 1 5 2 2 4 1 5 2 3 2...
result:
ok Good Job! (50000 test cases)
Test #7:
score: 0
Accepted
time: 34ms
memory: 13024kb
input:
42857 7 3 1 2 1 5 1 6 1 4 1 1 7 7 4 1 1 2 6 1 3 1 2 7 5 1 7 3 7 2 1 1 3 4 1 6 1 5 1 7 4 7 1 4 6 1 5 1 2 1 3 1 7 4 1 1 5 6 1 3 1 5 7 2 1 7 6 7 5 1 2 1 4 1 1 6 3 1 7 6 7 2 1 1 7 3 1 5 1 4 1 7 4 1 5 1 6 2 3 1 2 1 1 7 7 1 2 4 1 6 2 3 1 2 7 5 1 7 6 1 2 3 4 1 5 1 1 2 3 7 7 6 1 4 7 3 1 1 2 5 1 2 4 7 1 2 3 ...
output:
3 3 2 5 6 4 7 3 4 6 3 5 1 7 3 2 4 6 5 1 7 3 6 5 2 3 1 7 3 4 6 3 2 1 7 3 5 2 4 3 1 7 3 2 3 5 4 1 6 3 4 5 3 7 1 6 3 6 7 2 4 3 5 2 6 4 5 7 2 6 3 5 7 2 3 6 4 7 2 3 5 4 7 2 4 5 3 6 3 7 4 5 2 1 6 2 6 4 5 7 3 7 6 2 4 3 5 2 2 5 6 7 2 6 2 4 7 2 5 4 2 7 2 5 2 4 6 3 2 3 5 7 1 6 2 3 5 6 7 2 6 2 5 7 3 7 6 4 5 2 ...
result:
ok Good Job! (42857 test cases)
Test #8:
score: 0
Accepted
time: 41ms
memory: 9124kb
input:
37500 8 5 1 1 8 7 1 4 1 6 1 2 1 3 1 8 3 1 2 8 4 1 6 1 1 2 7 1 5 1 8 3 8 4 1 2 1 1 3 6 1 5 1 7 1 8 1 4 5 1 7 1 6 1 4 8 2 1 3 1 8 1 5 5 8 4 1 2 1 3 1 7 1 6 1 8 1 6 3 1 4 1 2 1 5 1 6 8 7 1 8 1 7 6 1 4 1 3 1 5 1 7 8 2 1 8 5 1 4 1 2 1 1 8 6 1 7 8 3 1 8 1 8 4 1 2 1 5 1 7 2 3 1 6 1 8 6 1 5 1 7 2 4 1 2 8 3 ...
output:
-1 3 3 4 6 7 5 8 3 4 2 6 5 7 8 3 5 7 6 2 3 8 3 4 2 3 7 6 8 3 3 4 2 5 7 8 3 6 4 3 5 2 8 3 5 4 2 6 3 7 3 8 4 5 3 6 7 -1 3 5 6 7 4 1 8 3 5 7 3 6 1 8 3 6 3 4 7 1 8 3 4 7 5 3 1 8 3 4 5 3 6 1 8 3 4 5 6 3 1 7 3 2 5 6 8 4 7 3 6 4 5 7 1 8 -1 3 5 2 6 7 1 8 3 7 4 6 2 1 8 3 4 5 7 2 1 8 3 4 6 5 2 1 8 3 5 2 4 6 1...
result:
ok Good Job! (37500 test cases)
Test #9:
score: 0
Accepted
time: 37ms
memory: 12936kb
input:
300 1000 815 567 883 63 783 506 485 779 142 248 218 214 617 238 481 567 20 203 119 212 953 179 44 830 427 156 97 916 763 172 484 512 916 21 417 958 408 257 238 634 891 213 90 208 394 56 758 819 435 26 636 718 880 212 458 662 123 212 239 156 548 314 852 436 722 828 271 429 493 27 910 421 354 143 956 ...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok Good Job! (300 test cases)
Test #10:
score: 0
Accepted
time: 110ms
memory: 26284kb
input:
3 100000 21854 12448 41900 78683 26279 40303 96957 78925 50096 72644 14704 14585 44195 23551 3290 42026 25017 64658 4593 10713 29129 13530 62892 43675 23793 13329 97502 10091 78766 44620 59301 95815 25781 93162 12231 24059 77637 66545 53889 84545 65596 58277 31337 87701 29049 43837 99301 2408 41562 ...
output:
-1 -1 -1
result:
ok Good Job! (3 test cases)
Test #11:
score: 0
Accepted
time: 143ms
memory: 50152kb
input:
1 300000 264872 86229 63995 164384 180167 260692 169708 168083 149321 50390 177160 60629 178607 170744 176734 60911 231963 17936 49668 90468 205798 261858 7645 12727 240590 1798 8446 139678 32309 208096 226620 119112 204528 63548 110330 250899 219366 144880 258130 23221 203423 40874 45194 78650 1571...
output:
-1
result:
ok Good Job! (1 test case)
Test #12:
score: 0
Accepted
time: 45ms
memory: 12504kb
input:
30000 10 1 6 4 8 7 5 6 10 3 1 8 2 2 9 9 10 5 9 10 3 7 2 6 6 9 1 6 4 10 9 10 5 6 7 2 8 3 10 8 10 6 3 2 1 3 2 1 10 7 4 5 2 9 8 4 9 10 4 1 6 8 2 10 9 10 7 2 5 2 8 7 1 6 3 1 10 6 2 3 6 9 6 7 10 8 2 2 1 5 3 1 4 4 10 10 2 8 3 6 5 7 7 8 1 6 8 10 9 2 4 6 6 10 10 1 5 4 3 6 4 7 1 2 3 5 9 8 2 3 10 9 6 10 2 7 5...
output:
2 3 4 9 7 3 1 5 6 8 6 4 3 1 7 1 5 2 6 3 4 3 1 5 2 9 4 1 7 1 8 2 9 6 5 3 3 4 1 9 8 5 2 7 10 3 8 3 3 9 1 2 1 5 4 1 10 1 4 5 9 3 2 3 2 3 1 7 6 4 3 1 9 5 10 3 8 3 1 5 8 4 1 6 3 8 10 2 4 3 5 4 1 7 10 4 9 5 9 8 3 5 6 3 8 2 9 4 1 7 5 9 8 6 10 3 3 1 9 8 5 3 7 3 5 4 1 2 7 3 3 10 6 4 9 3 7 3 1 6 10 2 9 8 3 1 ...
result:
ok Good Job! (30000 test cases)
Test #13:
score: 0
Accepted
time: 44ms
memory: 9204kb
input:
3000 99 79 72 72 6 1 90 94 89 31 28 59 89 78 85 73 35 57 45 45 99 38 57 11 70 26 14 92 13 35 52 30 18 61 15 29 86 60 22 5 57 17 84 36 84 70 37 10 86 80 91 34 87 65 8 42 88 87 25 88 43 8 47 33 78 62 47 15 73 83 77 24 33 97 38 23 77 20 34 85 32 55 22 63 10 66 30 39 5 28 62 89 15 37 49 16 75 74 66 47 4...
output:
32 3 93 94 59 61 89 17 36 74 84 50 9 69 82 83 23 60 55 1 95 88 53 43 56 44 67 45 97 57 76 58 26 14 22 27 16 4 48 47 77 85 11 78 24 33 41 47 65 8 19 54 80 54 79 47 7 86 81 52 51 30 40 86 63 35 59 25 51 60 14 74 27 96 87 42 34 71 26 62 1 8 98 47 11 13 45 29 45 88 33 2 33 70 79 37 18 12 6 91 18 39 17 5...
result:
ok Good Job! (3000 test cases)
Test #14:
score: 0
Accepted
time: 117ms
memory: 25528kb
input:
3 100000 83890 7467 75295 89651 4062 83955 60269 26734 58357 54437 22200 48174 87338 74094 86583 7977 1136 84701 34461 47665 82355 28324 32412 16170 5270 73823 37181 86410 22445 59139 27816 47294 540 79932 73768 41579 14577 92388 31765 75494 49018 24756 57215 90140 86438 22430 3974 15829 59053 22856...
output:
33627 53267 50266 1482 64339 59467 16458 93722 67154 36945 45051 59772 22368 24825 56421 28509 38789 76597 11004 98891 56338 44405 21899 52100 67457 35618 78456 25322 18841 36448 12219 81060 30909 91493 83965 53000 79620 75294 54025 36308 96838 8816 73678 93175 40229 94886 85642 64314 99446 21280 12...
result:
ok Good Job! (3 test cases)
Test #15:
score: 0
Accepted
time: 231ms
memory: 49408kb
input:
1 300000 30683 45175 202516 82288 209967 151196 160370 148366 36159 83057 277846 18399 58641 259342 220025 290125 299864 69137 276256 59853 163412 98854 211643 219357 45085 203080 17046 259484 175009 201826 220413 253746 280406 235850 107084 114346 6196 164024 149354 242637 8884 201047 102007 121900...
output:
100708 226276 227014 244586 40395 188774 290836 22242 123386 17215 61167 161969 39345 212598 223162 909 163934 49296 126480 148354 1463 67481 4526 196341 70734 285218 215131 35062 172630 148696 288769 296320 31419 217230 196311 245822 274493 240757 22777 145593 281676 158216 78719 239821 252202 2016...
result:
ok Good Job! (1 test case)
Test #16:
score: 0
Accepted
time: 228ms
memory: 80888kb
input:
1 300000 98923 244101 265083 199522 178854 130825 233559 275176 51110 162632 100454 144508 203138 94733 112144 116959 221684 184011 122356 174675 240265 56410 83529 213874 174757 59833 87918 98194 231431 71105 145121 105056 205429 60598 114418 168280 249115 124674 160102 183789 27460 854 72909 12628...
output:
2 1 250509 1 253307
result:
ok Good Job! (1 test case)
Test #17:
score: 0
Accepted
time: 161ms
memory: 49440kb
input:
1 300000 51552 258960 174014 1763 298103 122466 80039 102474 90881 123355 37816 182571 209856 199049 68745 246931 231305 147333 256217 77569 277988 49579 174054 154053 74959 60605 281490 278569 131850 7894 138112 208044 207380 67110 1334 204240 117581 152706 90835 142455 54402 68306 264004 244539 99...
output:
100828 29228 89842 97829 269471 285201 103004 80999 242128 185889 290155 131487 253584 79990 143261 9136 45120 16713 288334 162869 247657 256583 133377 142544 95257 203315 176084 77791 19215 15148 134541 216499 60639 172953 121477 25230 103531 158538 266278 257274 288970 35824 138947 176363 276119 1...
result:
ok Good Job! (1 test case)
Test #18:
score: 0
Accepted
time: 120ms
memory: 23508kb
input:
3 100000 43104 39350 58310 72159 1910 78304 366 33335 3494 5822 948 92660 11882 15212 69203 4346 45739 21275 65867 55409 61694 88089 71479 40349 35887 88786 52148 61962 82180 65178 93823 47701 43116 75915 86963 34539 50583 74229 40562 91601 12139 88394 52559 57679 25481 60170 31207 85832 4201 92027 ...
output:
33708 5914 94601 50688 20481 65889 36864 99605 15669 49199 55467 33433 35547 1734 57711 47540 73160 38370 18460 34893 11549 30957 39578 58887 63779 37654 79258 43747 85970 60014 14682 16035 98170 4185 50051 53665 80352 39919 49237 24574 43879 35242 6978 75546 83254 51109 98834 85532 46444 2343 90507...
result:
ok Good Job! (3 test cases)
Test #19:
score: 0
Accepted
time: 273ms
memory: 79824kb
input:
1 299999 153306 123584 100430 137396 151712 125355 180598 178628 178522 156317 6811 124889 41530 107031 35237 104587 235884 157908 130785 274651 141969 58315 203297 225663 192833 74643 223470 99863 272704 178999 163551 250862 133718 39962 199271 24737 159107 66084 139074 91207 229404 47856 273704 12...
output:
2 1 211007 1 141316
result:
ok Good Job! (1 test case)
Test #20:
score: 0
Accepted
time: 39ms
memory: 12264kb
input:
3000 100 9 37 30 16 87 75 66 20 89 79 78 72 48 5 62 100 61 95 69 93 23 86 18 48 32 24 91 43 54 93 92 63 15 7 6 92 67 35 65 89 8 26 21 98 1 65 40 85 36 41 77 39 56 44 69 70 46 67 80 60 94 96 14 36 34 99 84 62 22 74 23 79 46 19 27 51 11 14 18 70 85 8 73 6 97 40 71 83 41 98 61 87 2 90 45 5 20 44 17 81 ...
output:
2 1 2 1 25 2 1 82 1 31 2 1 82 1 48 2 1 95 1 51 2 1 58 1 88 2 1 51 1 31 2 1 14 1 98 2 1 33 1 95 2 1 29 1 41 2 1 22 1 80 2 1 11 1 90 1 1 57 2 1 75 1 7 2 1 25 1 80 2 1 26 1 60 2 1 53 1 14 1 1 63 2 1 17 1 7 1 1 8 2 1 100 1 33 2 1 54 1 50 2 1 11 1 57 2 1 30 1 88 2 1 28 1 99 2 1 69 1 23 2 1 87 1 34 2 1 32...
result:
ok Good Job! (3000 test cases)
Test #21:
score: 0
Accepted
time: 144ms
memory: 64804kb
input:
1 299999 123584 153306 137396 100430 114758 125355 180598 13155 156317 178522 124889 6811 41530 27377 104587 35237 157908 235884 130785 44576 141969 129416 225663 203297 120350 74643 20300 99863 295855 178999 198163 250862 133718 148059 24737 199271 66084 159107 91207 139074 229404 89529 273704 1565...
output:
149999 211007 37266 200879 11999 42721 60007 186847 27264 238901 168918 104377 128434 16950 166398 32487 54607 132405 36096 56533 259128 54072 104873 278891 248224 231355 51169 272859 6029 269039 270603 152728 274636 223096 212267 267911 21399 8757 220115 124154 44070 51060 145808 56725 235148 27976...
result:
ok Good Job! (1 test case)
Test #22:
score: 0
Accepted
time: 85ms
memory: 17336kb
input:
10 29999 29014 14470 26823 2725 13020 1832 9002 521 22160 26983 2964 2174 20830 22020 19201 4850 19060 10457 23936 2163 22700 29072 28735 4318 15942 8678 10533 9761 8946 29013 12121 555 14303 26560 18146 20485 16984 345 22717 347 21795 27399 20125 489 6200 24303 21419 17994 28274 28769 28326 25399 1...
output:
14999 2775 8776 11678 25755 25594 15475 461 22562 24659 6750 18880 4650 6053 7371 9476 17915 13357 21533 19027 19140 23088 15969 14170 22253 23182 20941 24488 4413 22031 1801 9030 7843 4928 27072 3438 9575 10543 16292 28239 24290 27148 4422 1202 23852 12834 25198 28114 8195 16961 24658 22780 29114 2...
result:
ok Good Job! (10 test cases)
Test #23:
score: 0
Accepted
time: 188ms
memory: 49988kb
input:
1 299999 258553 127891 200368 10642 134395 33327 66807 64283 298570 239432 106569 74919 101275 256095 215172 160205 258907 145255 294970 120844 120747 17359 231598 191111 103394 179995 276483 13575 153143 236649 32255 165538 13973 180565 114480 173795 280161 260850 239991 6207 137809 102438 160694 2...
output:
149999 150566 183289 56831 39022 171296 196533 58665 173825 93045 277670 198120 205575 143740 296022 228580 83922 4823 157760 153730 45095 144871 215781 13985 150634 188815 203807 298874 14698 51715 35007 24603 286626 216594 176218 36653 70137 238113 158405 247760 286765 9393 55136 25544 121236 1941...
result:
ok Good Job! (1 test case)
Test #24:
score: 0
Accepted
time: 80ms
memory: 16168kb
input:
10 29999 21547 280 5396 29060 21129 24483 1948 5302 5994 20221 12679 20525 23088 2218 24614 17646 9854 7760 23220 29541 9824 25475 9144 8680 17400 22930 3583 13702 14210 16949 4145 4827 4927 15200 5195 13939 23998 23812 20779 22916 19383 23442 29184 11705 12676 19405 4120 11612 24747 1107 25087 1775...
output:
14999 15275 24339 18281 9719 26302 29805 26068 17159 3819 20307 18583 10371 23226 23121 21418 27192 25389 29344 25438 18677 25218 6685 4690 3529 22675 19948 2938 16874 21424 25116 11769 19869 6026 17137 25083 22264 16957 29154 8964 20635 13590 7319 11422 1837 21070 28903 11337 4617 22963 153 19542 2...
result:
ok Good Job! (10 test cases)
Test #25:
score: 0
Accepted
time: 40ms
memory: 9104kb
input:
27000 11 3 5 11 3 2 3 7 1 10 8 8 6 9 8 3 1 8 4 1 8 11 3 1 1 2 5 6 11 1 6 9 10 6 4 8 1 5 1 7 5 8 11 1 3 6 11 4 6 10 1 1 8 2 6 7 11 1 9 11 1 6 5 11 3 7 6 8 11 3 9 6 3 8 6 4 1 8 5 9 10 3 2 9 11 8 5 6 8 11 5 8 2 7 11 4 5 8 9 3 10 3 11 8 1 11 7 3 2 3 9 1 8 10 8 1 9 5 3 9 4 1 6 8 11 3 11 8 5 8 1 6 8 11 8 ...
output:
5 5 11 10 6 9 4 7 8 1 2 5 9 10 3 2 11 7 1 6 5 4 5 4 2 3 10 8 9 1 7 11 5 5 5 2 9 4 7 11 1 6 8 10 5 6 2 1 9 8 4 5 7 11 10 5 7 2 10 6 8 4 1 5 9 11 5 4 2 10 9 5 6 11 7 1 3 5 11 9 3 2 1 8 6 10 4 5 5 6 7 10 3 9 2 11 8 1 4 5 7 2 4 3 10 9 1 11 6 5 5 4 11 10 9 6 8 2 7 1 3 5 8 11 7 9 5 6 1 2 10 4 5 8 3 9 10 6...
result:
ok Good Job! (27000 test cases)
Test #26:
score: 0
Accepted
time: 46ms
memory: 9188kb
input:
30000 6 5 3 6 2 4 1 1 3 2 1 4 4 2 1 4 1 3 11 9 1 10 11 11 3 11 9 4 6 3 7 2 11 1 6 1 5 8 9 17 6 15 10 7 8 17 13 11 3 8 15 4 16 3 12 4 15 10 2 6 6 9 5 13 5 14 2 1 10 5 8 15 14 14 5 1 6 12 4 8 14 5 9 13 5 4 9 1 13 7 13 5 3 11 14 5 10 2 13 12 3 6 5 1 8 3 12 2 12 7 5 4 9 4 11 10 6 12 12 5 4 11 17 15 11 1...
output:
2 4 5 1 6 1 3 2 4 10 2 5 4 1 8 9 7 7 1 9 6 12 15 7 10 14 5 11 15 17 8 16 5 8 11 14 3 7 2 6 10 5 12 4 2 7 1 8 5 9 4 10 6 2 13 3 4 1 7 14 9 8 12 10 11 6 5 3 2 11 7 9 1 10 8 4 8 12 -1 2 1 3 5 4 4 3 8 7 4 11 6 9 2 3 10 2 9 3 1 5 5 11 3 2 6 8 10 12 7 12 13 3 3 2 1 6 9 10 1 2 4 2 1 2 4 3 -1 1 1 3 1 3 2 4 ...
result:
ok Good Job! (30000 test cases)
Test #27:
score: 0
Accepted
time: 154ms
memory: 44708kb
input:
1 253253 50359 179100 159762 56963 156480 129546 194694 165531 171829 15612 8904 244239 167203 79755 59278 193676 6064 179420 93089 11873 208865 161063 72803 55831 6938 69443 182632 252034 15492 123140 26694 88239 59982 95642 209852 233064 205527 137224 222851 93508 28102 71250 250703 159154 54445 3...
output:
106864 223950 180757 122548 116462 64851 103725 55223 216887 221177 159333 216520 23265 236331 43297 168106 22048 158346 52494 24754 193303 81744 37590 161217 245460 221474 201725 174055 187695 74116 221939 219044 235889 86978 239512 192488 20039 199074 135126 27504 119815 212359 99109 27776 154995 ...
result:
ok Good Job! (1 test case)
Test #28:
score: 0
Accepted
time: 56ms
memory: 12592kb
input:
300 1855 1007 450 4 615 1845 844 426 65 1135 79 1020 1386 935 343 936 16 219 1370 1495 131 1409 13 1087 31 63 804 145 1689 1750 1731 694 623 243 626 418 1383 1396 990 1234 385 867 969 779 337 615 732 657 286 1134 1651 269 582 903 1755 478 1384 1360 1060 144 1082 217 1537 185 61 1634 1813 313 876 879...
output:
783 350 839 1837 1501 668 1760 1705 143 708 1102 746 764 1184 600 418 1451 1383 1672 349 446 539 486 545 1201 1289 603 745 1848 1234 710 662 1640 904 821 850 1618 1765 826 931 1433 1595 1058 541 434 197 1138 389 747 379 1403 1265 1013 1688 1531 236 729 1571 1745 1673 248 1769 170 1735 309 200 1439 5...
result:
ok Good Job! (300 test cases)
Test #29:
score: 0
Accepted
time: 161ms
memory: 49484kb
input:
1 297722 2542 280838 47066 211579 45334 161254 161254 3387 161254 81700 286925 161254 188708 161254 163323 239454 177641 142518 161254 141588 161254 289112 161254 132883 161254 264103 161254 7898 131553 35341 274424 85972 161254 111454 161254 245526 195088 87188 83391 252892 74347 144981 248942 2949...
output:
89178 3387 132883 270644 68163 20436 246556 19890 236659 274385 226548 284727 53468 11005 284069 18091 184285 293841 56233 280996 238721 200547 29370 82676 34253 13586 77147 14186 290507 253858 152639 91787 267309 277656 55 151857 229394 39287 33883 11638 248277 129516 229744 71984 88610 211677 1607...
result:
ok Good Job! (1 test case)
Test #30:
score: 0
Accepted
time: 170ms
memory: 49984kb
input:
1 297687 114063 114325 61315 256781 17004 254276 279378 173674 50685 133866 254276 270764 254276 168958 160573 254276 183000 144763 254276 41646 138547 226105 254276 62934 250757 284583 254276 147160 254276 62486 163839 23030 246684 80048 219153 38897 254276 184254 297273 295022 146005 254276 229491...
output:
124092 270764 168958 41646 62934 184254 146005 229491 145456 252959 104644 189341 253337 163051 57888 200344 207007 254389 75712 249620 101950 237609 81576 218065 245204 58006 65636 290928 25445 261720 151389 234350 5903 219255 63700 58358 228116 49500 152474 278936 174242 14923 25262 296258 234642 ...
result:
ok Good Job! (1 test case)
Test #31:
score: 0
Accepted
time: 142ms
memory: 50816kb
input:
1 298467 24310 131068 270342 284416 110818 163791 140749 270342 200509 156894 128257 270342 286273 39457 230236 150598 48559 18558 271934 270342 270342 221456 270342 240611 146171 270342 142089 270342 265273 37099 4824 207615 273677 270342 270342 233942 131877 270342 282024 14594 58550 270342 3225 1...
output:
149232 284416 271934 146171 233942 58550 112868 189495 67846 75457 249713 13857 54663 91537 112683 209627 259493 74652 239689 76406 213721 192529 164723 271532 255725 294830 1240 103260 85977 240991 88459 104162 86384 279116 72910 184749 234383 25509 75932 29350 126506 29905 33300 151337 135207 8113...
result:
ok Good Job! (1 test case)
Test #32:
score: 0
Accepted
time: 96ms
memory: 52032kb
input:
1 299096 43798 64829 64829 22308 25723 64829 125491 64829 132554 64829 64829 31091 82698 64829 161922 64829 64829 48363 153172 64829 198568 64829 64829 68075 246874 64829 64829 122620 64829 237999 64829 257438 44676 64829 64829 295759 64829 45750 64829 17755 195879 64829 86788 64829 172696 64829 648...
output:
-1
result:
ok Good Job! (1 test case)
Test #33:
score: 0
Accepted
time: 103ms
memory: 52180kb
input:
1 299097 55978 208819 55978 222666 55978 118386 176498 55978 177724 55978 55978 286400 7823 55978 55978 86011 258404 55978 55978 127466 55978 52857 34668 55978 31665 55978 55978 160320 55978 239002 290038 55978 55978 36827 55978 280050 55978 104777 55978 158847 52282 55978 206198 55978 55978 58412 1...
output:
149548 208819 222666 118386 176498 177724 286400 7823 86011 258404 127466 52857 34668 31665 160320 239002 290038 36827 280050 104777 158847 52282 206198 58412 158676 106284 130153 262744 83730 87284 98968 282354 295978 172986 247495 193012 69851 279835 169064 160705 58450 284089 16418 92496 263605 5...
result:
ok Good Job! (1 test case)
Test #34:
score: 0
Accepted
time: 98ms
memory: 52160kb
input:
1 299097 166438 82625 82625 128838 82625 141580 83485 82625 82625 210941 82625 40444 82625 45514 112980 82625 82625 8971 82625 240680 53717 82625 82625 243508 275918 82625 82625 214884 80291 82625 82625 244056 278345 82625 82625 50552 82625 84626 234287 82625 227857 82625 82625 282783 82625 169441 1...
output:
149548 166438 128838 141580 83485 210941 40444 45514 112980 8971 240680 53717 243508 275918 214884 80291 244056 278345 50552 84626 234287 227857 282783 169441 1413 143280 191958 153073 141476 148589 252875 85463 224039 269930 282876 282912 36413 6466 55929 73964 181852 1058 184784 149551 137909 2011...
result:
ok Good Job! (1 test case)
Test #35:
score: 0
Accepted
time: 108ms
memory: 52064kb
input:
1 299097 260330 58892 133029 58892 58892 172471 42729 58892 58892 26074 58892 99490 58892 3974 59464 58892 58892 186328 119256 58892 225649 58892 162394 58892 58892 128284 58892 215895 281775 58892 275533 58892 58892 149488 167782 58892 22771 58892 58892 63000 58892 9677 83128 58892 58892 121018 588...
output:
149548 260330 133029 172471 42729 26074 99490 3974 59464 186328 119256 225649 162394 128284 215895 281775 275533 149488 167782 22771 63000 9677 83128 121018 288822 66044 112020 277110 260473 68644 35006 99291 127209 200917 130518 235295 210701 57873 11396 249308 195229 159762 286320 120559 169660 28...
result:
ok Good Job! (1 test case)
Test #36:
score: 0
Accepted
time: 81ms
memory: 13444kb
input:
10 29462 10852 16001 15495 6444 21756 23481 23752 13053 21560 13691 9711 23194 24917 23476 13053 18916 5 8995 17585 23447 644 13053 27831 13053 22383 10656 15443 21538 10814 3308 4868 2089 23555 13053 25895 13053 12345 13893 13053 14041 13053 8611 4444 15324 23999 27186 27037 13053 23208 22273 22940...
output:
8881 8611 14277 13566 2602 28122 9310 1390 1354 9856 17664 19486 11369 20171 24043 26106 21268 23422 3166 5881 1647 22740 25902 25477 7274 9342 2384 24330 15691 14861 2269 4033 6605 1489 16245 7982 25255 20367 6439 3941 19128 10224 1180 29430 3826 9576 20754 23047 25572 11776 24403 24122 1763 16363 ...
result:
ok Good Job! (10 test cases)
Test #37:
score: 0
Accepted
time: 47ms
memory: 12856kb
input:
100 2959 1769 2187 2304 2429 2635 1931 271 2342 1671 153 707 1154 2597 1668 1048 204 1242 1301 926 2013 1557 2752 488 1893 613 1809 1416 2395 120 1179 982 321 2686 86 2313 2009 878 848 1447 2207 728 1885 2812 1683 1290 1627 2701 135 933 1099 1719 393 2355 2519 1368 384 311 1080 823 1642 459 2670 266...
output:
98 2022 2596 1 2235 2824 486 2824 1879 2824 2397 2824 1903 2824 804 2824 31 2824 2300 2824 1191 2824 1228 2824 1477 2824 234 2824 1865 2824 1766 2824 2066 2824 1984 2824 2377 2824 1428 2824 1457 2824 2525 2824 2193 2824 1885 2824 2329 2824 655 2824 1854 2824 293 2824 1967 2824 13 2824 2879 2824 2535...
result:
ok Good Job! (100 test cases)
Test #38:
score: 0
Accepted
time: 41ms
memory: 9296kb
input:
1000 294 200 192 200 46 43 256 85 47 98 12 127 200 111 127 257 124 168 32 45 274 197 49 200 27 144 38 156 256 148 202 200 80 31 248 35 66 282 128 60 200 189 37 88 54 238 280 44 245 46 263 220 53 144 200 200 55 58 184 200 153 84 173 31 284 24 170 200 211 22 244 232 242 200 208 188 26 139 154 251 104 ...
output:
86 208 191 172 258 125 69 182 169 293 235 62 103 206 142 279 285 278 215 1 188 1 73 200 122 200 116 200 259 200 207 200 261 200 205 200 244 200 135 200 93 200 281 200 51 200 193 200 165 200 114 200 291 200 128 200 140 200 209 200 216 200 222 200 85 200 254 200 260 200 267 200 6 200 74 200 94 200 40 ...
result:
ok Good Job! (1000 test cases)
Test #39:
score: 0
Accepted
time: 150ms
memory: 51044kb
input:
1 299997 253129 238438 256990 147794 56683 265606 62100 74831 58006 231602 227120 138613 72936 16010 271383 221839 110579 31739 13864 11106 196180 159069 78858 61661 262511 279235 45738 172410 2512 6066 144552 29625 194524 184023 196218 229474 256817 33532 166763 175023 188106 91596 93278 158818 280...
output:
149998 110766 39235 184037 75643 55782 147480 277141 125801 136463 263863 219409 99612 214095 174683 72711 141778 241022 71458 232694 133696 158503 43547 85732 235721 59455 259656 289444 266934 35970 277856 121560 153980 298879 95512 92956 180176 203248 30891 240639 190141 161059 217216 132591 20439...
result:
ok Good Job! (1 test case)
Test #40:
score: 0
Accepted
time: 150ms
memory: 50808kb
input:
1 299995 251405 13382 21412 273614 170998 239060 142811 89087 163686 80590 54073 23173 29717 93866 155059 150414 171846 663 218307 10405 252692 83378 131202 289721 52385 252854 293096 280491 216796 237285 242784 243233 52784 6922 68312 26488 205497 147202 65036 297840 58601 67107 164525 57839 167843...
output:
149997 141921 90699 155348 17085 176596 290896 295087 279499 267088 141600 215458 50814 215516 210135 171745 6883 119417 9880 263772 50991 34855 267989 186288 106607 209285 183228 164952 137723 131678 230140 102582 41335 51508 9575 171473 34339 296012 114860 152329 233886 240653 238347 92538 11305 2...
result:
ok Good Job! (1 test case)
Test #41:
score: 0
Accepted
time: 149ms
memory: 50828kb
input:
1 299993 5467 110867 249637 87281 209055 74176 170317 272027 19928 97403 158898 19368 120942 93881 150886 63314 221175 188504 125295 79790 241291 263489 258417 196595 157362 130040 163372 85682 261036 45856 257946 163512 54262 17552 251249 14029 213457 65927 265238 36030 4861 71772 159755 111439 375...
output:
149996 211547 29176 223263 45275 113399 109262 6392 228505 271088 98492 56253 112361 150004 120958 80836 44096 134433 114604 178992 77599 79956 105128 48804 80480 258148 177243 31547 40965 131603 3329 274401 237431 282027 138274 114229 213954 30824 184128 201127 199442 108449 131556 52286 147401 195...
result:
ok Good Job! (1 test case)
Test #42:
score: 0
Accepted
time: 145ms
memory: 50872kb
input:
1 299991 248982 174625 105559 244297 35265 128781 206509 158409 13863 41023 249166 59270 215265 188850 218206 113138 126624 205065 241101 283870 31511 34427 237845 182965 134293 221193 214509 104965 67564 158810 198261 216053 115921 200242 245392 107170 62619 285117 48060 132083 166094 84748 150023 ...
output:
149995 156084 200138 118203 23493 157760 104563 154243 125740 147119 95269 62968 123149 184316 279344 227222 156518 130286 55108 229697 271484 189964 103689 102104 179955 113415 106095 22128 65490 142498 32489 222394 207624 217859 210055 297420 88204 261112 115205 47192 76215 295361 231005 182191 20...
result:
ok Good Job! (1 test case)
Test #43:
score: 0
Accepted
time: 153ms
memory: 49448kb
input:
1 299999 185541 176688 252501 252009 201515 181336 174664 10052 235206 78841 271650 240453 177704 41444 30343 236755 136584 224074 123830 176470 119252 294416 176341 111829 241834 52983 35945 184402 68227 225761 146133 151540 249663 70136 156441 42951 95322 152829 259090 103376 84766 152588 150129 1...
output:
149999 58203 136809 173725 119346 98539 199425 50238 126050 34814 194806 143019 229278 263691 250316 60522 11848 104218 133042 250887 187982 271206 264754 29097 124026 273560 167961 83089 44178 160794 91669 130969 21558 165994 195168 255281 54713 31219 129417 149420 223234 61385 144975 193672 129373...
result:
ok Good Job! (1 test case)
Test #44:
score: 0
Accepted
time: 163ms
memory: 49328kb
input:
1 299997 46586 268160 120257 162918 155586 87070 233774 236522 195573 139640 213343 184602 26338 174317 236326 103114 246267 241694 166020 217647 73806 217138 115817 291894 296219 281396 231138 217264 57086 215561 296205 295067 174916 36910 262907 177629 268640 277927 33944 172724 299448 298104 2913...
output:
149998 106517 36951 56453 61738 203032 211268 212089 25748 117599 118630 76514 135302 238561 1246 70974 252509 83334 130267 45185 141546 119216 24614 153267 16242 183414 35725 183332 205413 111795 141577 168170 27012 17307 176984 192334 97274 124848 112241 1558 72948 220952 109518 170168 221243 2084...
result:
ok Good Job! (1 test case)
Test #45:
score: 0
Accepted
time: 42ms
memory: 13480kb
input:
100 2997 1842 108 983 1626 2076 2280 1960 2673 2029 1154 1506 836 144 1843 173 1775 322 1567 1632 1092 2608 2819 2737 2888 24 2046 400 2487 2396 2569 2072 1695 2223 2237 2175 592 694 2236 2523 2322 2211 2325 2196 2888 1509 1586 2376 2272 2063 2310 2471 2612 2530 2101 1618 25 1830 1404 2646 743 2256 ...
output:
1498 1008 154 692 1802 1029 232 841 214 2043 391 262 1334 2219 2282 1791 2550 2143 2635 1353 1225 1933 1227 1183 2403 804 2691 1147 401 2692 2633 2725 2796 87 317 25 1511 770 341 721 1952 55 724 2099 240 2003 2142 215 349 2166 723 389 2224 333 2278 2413 2348 1425 79 1639 45 808 1678 2155 1389 713 10...
result:
ok Good Job! (100 test cases)
Extra Test:
score: 0
Extra Test Passed