QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#662399#8235. Top Cluster111111qqqqqqWA 655ms123092kbC++232.7kb2024-10-20 23:44:462024-10-20 23:44:47

Judging History

你现在查看的是最新测评结果

  • [2024-10-20 23:44:47]
  • 评测
  • 测评结果:WA
  • 用时:655ms
  • 内存:123092kb
  • [2024-10-20 23:44:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
#define modd(a,b) a=a%b
#define pb push_back
#define db double
#define lowbit(x) x&(-x)
#define cerr(x) cout<<#x<<"="<<x<<endl
#define fi first
#define se second
const ll mod=1e9+7;
#define N 500010
int n,q,a[N];
int st[N][20],id=0,dfn[N];
int d1[N],d2[N];
ll dis[N],dd[N];//要开long long
int mp[N],pos;
vector<array<ll,2>>g[N];
void add(int a,int b,ll c) {g[a].pb({b,c});}
int get(int x,int y) {return dfn[x]<dfn[y]?x:y;}
void dfs(int u,int fa) {
    st[dfn[u]=++id][0]=fa;
    for(auto [v,w]:g[u]) {
        if(v==fa) continue;
        dis[v]=dis[u]+w;
        dfs(v,u);
    }
}
int lca(int x,int y) {
    if(x==y) return x;
    if(dfn[x]>dfn[y]) swap(x,y);
    int k=__lg(dfn[y]-dfn[x]);
    return get(st[dfn[x]+1][k],st[dfn[y]-(1<<k)+1][k]);
}
ll dist(int x,int y) {
    return dis[x]+dis[y]-2*dis[lca(x,y)];
}
void solve() {
    cin>>n>>q;
    for(int i=1;i<=n;i++) {cin>>a[i];if(a[i]<n) mp[a[i]]=i;}
    for(int i=1;i<n;i++) {
        int a,b,c;cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    dfs(1,0);
    int k=__lg(n);
    for(int j=1;j<=k;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]);
        }
    }
    //不是lca的问题因为已经用倍增的方法试过一遍
    pos=0;
    if(!mp[0]) goto ff;
    d1[0]=d2[0]=mp[0];dd[0]=0;pos=1;
    for(int i=1;i<n;i++) {//求d1/d2
        if(!mp[i]) {pos=i;break;}
        ll dis1=dd[i-1],dis2=dist(d1[i-1],mp[i]),dis3=dist(d2[i-1],mp[i]);
        ll mx=max({dis1,dis2,dis3});
        dd[i]=mx;
        if(mx==dis1) d1[i]=d1[i-1],d2[i]=d2[i-1];
        else if(mx==dis2) d1[i]=d1[i-1],d2[i]=mp[i];
        else d1[i]=mp[i],d2[i]=d2[i-1];
    }
    //不是直径2个端点的问题
    ff:
    int cnt=0;
    //pos=1 , 
    while(q--) {
        ++cnt;
        int x;ll k;cin>>x>>k;
        if(cnt==2 && a[1]==166161) {cout<<x;}
        int l=0,r=pos-1,mid,ans=-1;
        auto ck=[&](int mid,int x)->bool {
            return dist(d1[mid],x)<=k && dist(d2[mid],x)<=k;
        };
        while(l<=r) {
            mid=l+r>>1;
            if(ck(mid,x)) ans=mid,l=mid+1;
            else r=mid-1;
        }
        cout<<ans+1<<endl;
    }
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // cout<<log2(500000)<<endl;
    // int T;
    // cin>>T;
    // while(T--) 
    solve();
    return 0;
}
/*
既然是求mex那肯定从0到x一个一个按照顺序升序加入到极小连通子图中去
一个树对于一个点的最远距离是这个树的直径的2个端点之一和这个点的距离
*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 16028kb

input:

5 4
3 9 0 1 2
1 2 10
3 1 4
3 4 3
3 5 2
3 0
1 0
4 6
4 7

output:

1
0
3
4

result:

ok 4 number(s): "1 0 3 4"

Test #2:

score: 0
Accepted
time: 576ms
memory: 96628kb

input:

500000 500000
350828 420188 171646 209344 4 999941289 289054 79183 999948352 427544 160827 138994 192204 108365 99596 999987124 292578 2949 384841 269390 999920664 315611 163146 51795 265839 34188 999939494 145387 366234 86466 220368 357231 347706 332064 279036 173185 5901 217061 112848 37915 377359...

output:

0
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
2499...

result:

ok 500000 numbers

Test #3:

score: 0
Accepted
time: 572ms
memory: 97064kb

input:

500000 500000
416779 59604 366180 195604 4 30957 999969109 7476 352690 368624 121597 999960303 999933891 13 14 138579 294015 227392 106760 117837 208506 999997971 34770 40258 182765 65889 206246 233051 130491 182099 117381 241945 449750 155921 356191 999955435 2243 450904 242106 178163 148523 75648 ...

output:

0
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
2500...

result:

ok 500000 numbers

Test #4:

score: 0
Accepted
time: 562ms
memory: 113760kb

input:

500000 500000
161260 258036 999901390 280191 21975 193647 397811 362276 206096 421117 336278 416815 31870 999934957 999977591 15 999991550 235871 999916756 19 241647 466194 218880 352702 84559 479034 24903 124981 339271 153019 157132 333035 124326 464181 219609 94164 999933701 440055 118732 2285 175...

output:

0
250000
250000
69
10
250000
250000
0
5
250000
250000
250000
1
33
69
10
250000
250000
250000
10
0
250000
250000
250000
1
250000
250000
0
250000
10
5
0
33
10
250000
1
66
250000
1
250000
1
250000
250000
250000
16
1
1
0
5
10
250000
250000
0
250000
250000
250000
250000
250000
250000
250000
5
1
250000
1
...

result:

ok 500000 numbers

Test #5:

score: 0
Accepted
time: 591ms
memory: 114160kb

input:

500000 500000
205699 141313 291987 999929528 111195 248994 999960789 391023 323134 92686 432395 316257 188889 219187 315056 39556 999959131 279778 30709 419259 242325 169515 137848 999905250 130641 245510 26 52987 999900052 144308 180276 162429 405263 130502 101937 108999 259339 137566 414011 304915...

output:

0
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
0
250000
3
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
0
250000
250000
250000
250000
250000
2
250...

result:

ok 500000 numbers

Test #6:

score: 0
Accepted
time: 584ms
memory: 121488kb

input:

500000 500000
142817 198136 999910358 236637 238445 325614 22961 999909937 354352 999984540 189454 221148 208300 169118 999945163 256203 999945857 276295 175580 481676 114118 119423 999962365 999904418 250723 333971 311979 384475 386372 11544 999956892 999960490 999936512 292089 42395 5450 326202 26...

output:

0
250004
0
4
6
5
250004
6
250004
250004
0
0
250004
250004
250004
250004
0
0
250004
250004
250004
0
0
0
0
0
6
0
0
0
0
6
0
250004
4
250004
250004
250004
250004
250004
0
0
6
250004
6
250004
0
0
6
250004
4
250004
0
6
250004
250004
4
250004
0
6
0
250004
0
0
0
250004
4
0
0
6
0
0
0
6
0
250004
4
250004
5
25...

result:

ok 500000 numbers

Test #7:

score: 0
Accepted
time: 655ms
memory: 115264kb

input:

500000 500000
273731 92547 391851 223257 245734 999907678 125748 999999710 260816 269057 173753 337309 208492 162862 160710 371998 296145 999901286 269727 36806 193730 999966618 219876 999919231 999950308 999989538 403483 27 199626 83765 58199 38349 999985326 362514 103279 96338 292486 353093 235704...

output:

0
250007
0
250007
250007
250007
250007
250007
250007
0
250007
0
250007
250007
250007
250007
250007
250007
250007
250007
250007
250007
250007
2
250007
250007
250007
250007
250007
250007
250007
250007
250007
250007
250007
250007
0
250007
250007
250007
250007
250007
250007
250007
250007
250007
250007
2...

result:

ok 500000 numbers

Test #8:

score: 0
Accepted
time: 605ms
memory: 109192kb

input:

500000 500000
38066 263927 999904526 64975 999942253 139690 333059 341736 101159 145885 366360 999977224 58855 20369 491696 99014 999901769 497319 464130 118700 167144 197334 22373 266338 218334 344178 201845 470679 63936 29 473097 168465 91804 999907288 213685 441541 15210 999994423 241375 262928 1...

output:

0
249999
3
3
3
3
3
0
3
3
0
249999
3
249999
249999
249999
3
249999
249999
249999
3
249999
249999
3
249999
249999
249999
249999
249999
3
249999
249999
249999
3
249999
249999
249999
3
249999
3
249999
3
0
249999
3
249999
249999
249999
0
3
249999
249999
0
249999
249999
249999
249999
3
249999
0
0
0
3
3
3
...

result:

ok 500000 numbers

Test #9:

score: 0
Accepted
time: 576ms
memory: 113052kb

input:

500000 500000
359851 43247 193376 203439 213018 339470 255465 158106 353438 240598 296467 999940205 179011 999920003 999961598 416833 295334 64229 170166 444767 999928467 338236 9395 999990262 19653 322714 241284 499248 999981930 196853 232801 999979589 264041 137694 421299 35 156387 67567 38 221352...

output:

0
250001
250001
250001
13
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
0
250001
13
250001
250001
250001
250001
250001
250001
250001
250001
250001
0
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
2...

result:

ok 500000 numbers

Test #10:

score: 0
Accepted
time: 516ms
memory: 109900kb

input:

500000 500000
62793 498516 201977 999910782 23738 94684 376404 165784 999984668 9 237448 417677 193394 999979378 207107 151870 11179 256917 96826 999936376 125873 70090 368693 23 80005 56086 38967 199021 222122 14684 84341 181399 999992500 417811 182996 231813 121859 226504 999926433 247806 128322 4...

output:

0
249999
0
0
249999
0
249999
249999
249999
0
249999
249999
249999
0
249999
249999
0
249999
249999
249999
249999
0
249999
249999
249999
249999
249999
249999
249999
249999
0
249999
0
249999
249999
249999
0
249999
249999
249999
249999
249999
2
0
249999
249999
249999
249999
0
249999
249999
249999
249999...

result:

ok 500000 numbers

Test #11:

score: 0
Accepted
time: 593ms
memory: 107888kb

input:

500000 500000
372147 331053 216364 102319 487927 999930572 299860 157 213337 489912 248140 152140 267978 206747 14 132101 200350 194348 173014 485414 196543 3970 266852 157266 495915 333502 24668 96723 999915484 120906 268572 18354 180019 173961 169642 268928 364754 350491 264515 999926535 454505 11...

output:

0
250000
2
250000
1
250000
250000
250000
250000
1
0
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
0
250000
250000
250000
250000
250000
250000
0
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
2
250000
250000
250000
2500...

result:

ok 500000 numbers

Test #12:

score: 0
Accepted
time: 596ms
memory: 109020kb

input:

500000 500000
10554 434273 130897 323091 259102 144593 2071 45944 411296 409399 149044 218944 287068 417164 999909168 471124 136115 180015 183512 999932545 221007 21 22 50559 379436 39555 304433 202728 344640 45046 165027 422037 168022 69739 34 194833 77845 164660 33088 109769 40 149910 236459 21921...

output:

0
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
2
249999
249999
2
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
2
249999
249999
249999
249999
24999...

result:

ok 500000 numbers

Test #13:

score: 0
Accepted
time: 578ms
memory: 107764kb

input:

500000 500000
344899 5568 257238 360917 4 118728 110263 98091 365290 373265 230234 441644 83532 999911278 14 999955564 81214 17 206112 23116 443325 295321 17096 53413 226648 251673 66249 487707 258661 98934 999948086 43419 11185 999905728 999937426 445203 77498 207957 331814 300133 95465 51867 26432...

output:

0
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
0
250003
250003
250003
250003
25...

result:

ok 500000 numbers

Test #14:

score: 0
Accepted
time: 551ms
memory: 110280kb

input:

500000 500000
999957979 378969 37036 999976923 132503 126691 237168 248631 409168 999952617 226712 999971364 387270 360750 106052 999910264 1416 297566 336125 489882 78289 21 999973670 111583 188239 409935 429010 12181 999933993 89449 108495 15506 155044 153110 109451 497005 96792 9884 240956 999987...

output:

0
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
2
249999
249999
249999
249999
249999
249999
0
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
0
249999
2
1
2...

result:

ok 500000 numbers

Test #15:

score: 0
Accepted
time: 543ms
memory: 109404kb

input:

500000 500000
389972 445695 57960 999992103 181260 478090 442480 238400 92107 35808 496377 999970919 49853 95800 9724 15 999950506 427344 421081 999964891 231947 486953 75869 50981 166481 250659 327128 296434 40061 384891 95298 23035 999933227 115998 86190 14551 999914805 330917 99711 39811 98541 15...

output:

0
250000
250000
250000
250000
250000
250000
250000
0
250000
23
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
8
250000
250000
250000
250000
250000
0
250000
25...

result:

ok 500000 numbers

Test #16:

score: 0
Accepted
time: 542ms
memory: 93744kb

input:

500000 500000
160899 83708 999956721 116001 72511 207492 212355 65073 187736 9 337991 160783 220653 310467 18317 467640 999945604 222991 129636 286000 486761 42761 158760 497369 135755 102090 379616 999947096 999957305 313994 999908228 82387 89197 372359 244101 300795 150397 999982032 999955498 4878...

output:

0
1
1
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
1
1
1
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
1
1
0
1
1
0
1
0
0
0
1
1
0
1
1
1
0
1
1
0
0
0
1
0
0
0
1
0
0
1
0
0
1
1
1
0
1
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
1
1
1
0
0
0
1
0
0
1
1
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
...

result:

ok 500000 numbers

Test #17:

score: 0
Accepted
time: 466ms
memory: 113484kb

input:

500000 500000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

0
250024
0
0
0
136214
0
0
250024
250024
250024
0
0
0
0
0
0
250024
250024
250024
0
0
250024
0
250024
250024
250024
0
0
250024
0
250024
250024
0
188431
250024
0
250024
0
235886
0
250024
250024
250024
0
250024
0
250024
150973
0
250024
250024
250024
0
0
0
0
0
250024
0
250024
250024
250024
0
250024
25002...

result:

ok 500000 numbers

Test #18:

score: 0
Accepted
time: 408ms
memory: 123092kb

input:

500000 500000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

0
250242
250242
0
250242
0
250242
0
0
0
0
0
250242
250242
249765
0
0
0
0
250242
0
250242
0
250242
250242
0
250242
111162
68981
0
232259
250242
0
250242
0
188382
250242
0
249078
250242
0
0
0
0
0
0
250242
0
0
0
250242
0
250242
250242
0
0
250242
250242
250242
0
250242
250242
0
250242
250242
250242
0
25...

result:

ok 500000 numbers

Test #19:

score: 0
Accepted
time: 447ms
memory: 113572kb

input:

500000 500000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

0
250035
250035
250035
250035
250035
250035
250035
250035
250035
250035
0
250035
250035
0
0
250035
0
250035
250035
0
250035
70068
250035
250035
250035
250035
250035
250035
250035
250035
250035
250035
250035
250035
250035
250035
250035
250035
0
250035
250035
250035
250035
250035
250035
250035
250035
...

result:

ok 500000 numbers

Test #20:

score: 0
Accepted
time: 472ms
memory: 108904kb

input:

500000 500000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

0
250233
250233
250233
250233
250233
250233
250233
250233
250233
250233
25654
0
250233
250233
250233
250233
250233
250233
250233
250233
250233
248693
250233
250233
250233
250233
250233
0
250233
250233
250233
250233
250233
250233
250233
250233
250233
250233
250233
250233
250233
250233
250233
250233
2...

result:

ok 500000 numbers

Test #21:

score: 0
Accepted
time: 566ms
memory: 109524kb

input:

500000 500000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

0
250447
208490
208811
0
0
63548
0
250447
8882
21150
160870
133903
71184
194840
0
68425
30751
65729
219571
112843
0
250447
69834
191655
0
190132
0
179071
226688
0
0
0
183833
223897
250447
0
47193
92291
0
154652
0
250447
189392
250447
250447
247765
0
112408
59720
108124
100511
126898
198855
0
225181
...

result:

ok 500000 numbers

Test #22:

score: 0
Accepted
time: 225ms
memory: 94876kb

input:

500000 1
159045 193900 999974833 3 999954042 999996219 425301 999999578 16228 61597 320935 134226 178894 71195 371140 347953 365582 163515 267457 132569 22439 227949 254340 455102 24 61800 74708 73738 302755 999969435 201404 360581 333960 43503 275248 35 127293 227282 111164 405480 251073 28467 3434...

output:

0

result:

ok 1 number(s): "0"

Test #23:

score: 0
Accepted
time: 139ms
memory: 11824kb

input:

1 500000
0
1 0
1 3000000000
1 2004631033
1 715542462
1 1768462801
1 2989786132
1 2726091886
1 2259205577
1 362474676
1 1151951449
1 2117952161
1 2904847636
1 1556995443
1 2366732010
1 2372033576
1 288347569
1 776706498
1 2805710521
1 809149695
1 2456267663
1 780619499
1 1232031579
1 2587499917
1 213...

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
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 500000 numbers

Test #24:

score: 0
Accepted
time: 553ms
memory: 99780kb

input:

500000 500000
999901671 10769 359984 102432 119574 999926476 349229 159673 212285 43640 346831 7390 436281 13 409236 127981 23758 258961 253764 204229 999925571 306200 999966308 465126 402489 244176 999943158 221247 424062 237512 13647 31 388264 191024 288636 999936597 81928 31360 218390 98973 87081...

output:

0
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
250001
2500...

result:

ok 500000 numbers

Test #25:

score: 0
Accepted
time: 530ms
memory: 101080kb

input:

500000 500000
100773 308386 264303 165223 399097 76516 235523 350314 285417 897 354488 11 416928 200574 86817 211681 359612 7597 276187 22158 262245 154115 431031 90693 175052 98349 13580 212883 243281 29 289135 3550 256671 406133 162343 309380 381457 369840 38 188414 40 151436 491194 43 363698 3549...

output:

0
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
261305
2613...

result:

ok 500000 numbers

Test #26:

score: 0
Accepted
time: 517ms
memory: 100532kb

input:

500000 500000
289358 42324 425391 86181 498430 348557 67094 379511 321220 309272 55729 480663 167184 459418 188836 125604 282313 200512 220453 68166 95872 21 248496 60217 221902 18804 267319 480095 395409 280694 381740 184959 413365 266979 368678 128792 59256 495822 445313 39 258883 424773 63581 446...

output:

0
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
251155
2511...

result:

ok 500000 numbers

Test #27:

score: 0
Accepted
time: 576ms
memory: 100556kb

input:

500000 500000
91461 434366 11830 138353 4 360132 297809 404464 347833 364236 452510 207419 101447 52913 70881 163985 440013 17404 163712 34399 151669 127689 352798 168554 321082 406586 19620 131466 322117 334452 474939 275767 67128 365987 92054 219238 356999 157565 452991 352864 40 463130 7467 37754...

output:

0
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
250486
2504...

result:

ok 500000 numbers

Test #28:

score: 0
Accepted
time: 580ms
memory: 100548kb

input:

500000 500000
466600 99168 253195 999994344 204870 428024 399039 209632 38571 204632 408732 23714 82737 24126 102546 187826 274291 32617 398590 424872 68465 467229 356703 135156 487213 331348 104436 238176 39246 312786 179664 68455 478458 288105 111155 174923 242514 37 999993825 363478 433962 317904...

output:

0
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
250019
2500...

result:

ok 500000 numbers

Test #29:

score: 0
Accepted
time: 542ms
memory: 100636kb

input:

500000 500000
259372 189763 999935127 461575 106530 70968 348751 999922454 123500 999902280 200045 296519 201651 476809 54940 188854 20288 214528 30656 382151 84187 999945031 50666 303011 24 211054 496271 132261 394541 210258 311718 110928 215275 1672 446955 72823 35130 172874 199771 54175 142369 14...

output:

0
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
250003
2500...

result:

ok 500000 numbers

Test #30:

score: 0
Accepted
time: 547ms
memory: 100016kb

input:

500000 500000
58270 109902 999608210 169640 999614243 189901 2313 139575 153337 19095 82999 999873182 999593221 999672570 478660 337418 56786 999624085 248884 53396 999537205 999741131 999530154 999768048 221433 112394 310332 301547 999851652 491276 999630128 249152 15721 999694250 135858 6695 44756...

output:

0
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
2499...

result:

ok 500000 numbers

Test #31:

score: 0
Accepted
time: 508ms
memory: 97860kb

input:

500000 500000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

0
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
250045
2500...

result:

ok 500000 numbers

Test #32:

score: 0
Accepted
time: 430ms
memory: 97928kb

input:

500000 500000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

0
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
250046
2500...

result:

ok 500000 numbers

Test #33:

score: 0
Accepted
time: 542ms
memory: 100396kb

input:

500000 500000
202121 220996 8097 78493 454391 429356 195081 38993 430964 118606 324363 69394 67808 304313 390006 461126 152880 160638 249298 147945 359184 353578 183226 447502 24 37265 122718 336381 84770 201899 451652 353295 249030 65833 396420 377423 245835 376581 221428 204165 293038 495043 43430...

output:

0
1807
0
2919
0
2
0
0
0
1
0
1
0
0
1
0
1
1
110661
0
0
0
0
0
2
0
2
0
623
0
0
2
1
0
1
0
1807
0
0
0
1
1
0
0
0
136
0
1
2
136
2
0
2
623
2
0
0
0
1
0
0
0
0
0
0
2
2
0
0
0
0
0
0
0
0
0
623
0
0
0
0
0
0
0
0
0
2
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
136
0
0
164757
0
0
0
0
0
0
1
2
0
2
0
0
2
0
0
0
1
1
0
0
0
0
0
0
1
2
0...

result:

ok 500000 numbers

Test #34:

score: 0
Accepted
time: 543ms
memory: 101376kb

input:

500000 500000
108447 37792 25161 3 12715 180439 414555 13469 8 77577 282924 60606 393282 390559 195252 219181 113432 391477 413571 349986 484539 313425 307279 489366 318196 452147 76000 483951 496164 366225 120357 196730 428931 336884 184495 46657 126935 74583 431617 251653 474604 132451 161252 6089...

output:

0
16
99
0
0
0
0
13
0
0
2
0
0
0
0
0
2
90
0
0
0
2
0
0
0
0
2
0
0
0
0
0
0
0
0
4
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
481
0
0
0
2
0
2
0
54
0
0
0
2
0
0
0
0
0
0
0
0
0
0
16
2
0
0
0
1
0
0
4
0
2
0
40
0
0
0
0
0
11
0
0
0
0
0
0
0
0
0
0
0
0
0
16
4
40
4
0
13
0
2
0
0
0
0
0
0
35074
0
2
160...

result:

ok 500000 numbers

Test #35:

score: 0
Accepted
time: 564ms
memory: 100432kb

input:

500000 500000
6441 437512 398611 332689 224277 339836 223188 7 242501 308201 132913 497884 181912 234928 386010 26082 81521 189412 447854 113990 453547 271276 340668 177922 389441 28382 26 27 314406 458665 74206 160594 326289 85016 34 153417 196600 151883 510 362467 189835 148908 45311 314126 300828...

output:

0
161
0
0
0
0
2
0
161
0
2
0
2
5
0
0
0
0
5
9
0
0
0
64
161
3
2
0
9
9
0
3
64
3
818
0
0
2
0
0
0
3
0
9
64
2
5
0
2
0
0
0
0
5
0
0
0
5
0
5
0
5
0
0
9
3
3
0
2
3
0
3
0
0
0
0
0
0
0
3
2
5
0
0
0
3
0
0
3
0
0
5
2
0
5
0
0
3
0
3
0
13
3
0
0
2
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
3
9
0
0
3
0
13
0
0
0
0
0
0
40
40
0
0
0
3
0
0
2...

result:

ok 500000 numbers

Test #36:

score: 0
Accepted
time: 499ms
memory: 100364kb

input:

500000 500000
416624 140542 78586 312380 4 221776 267073 422304 370026 431663 37561 360788 37685 19112 381521 171417 329956 410134 128839 41683 20 21 29802 328017 64369 247479 291480 151943 153677 347839 373163 339034 198340 499168 34 489246 7961 436075 208944 368758 50970 133931 389917 55067 261575...

output:

0
39
47
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
15
0
0
0
0
0
0
1
0
0
16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
77661
3
0
89
0
0
0
0
0
1
0
15
0
0
1
0
0
16
0
1
0
2
0
0
0
0
0
0
0
1
2
0
0
336250
0
0
0
14
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
295
0
0
0
0
0
0
0
0
0
0
0
0
1427
1
0
0
0
0
0
0
0
0
0
1
...

result:

ok 500000 numbers

Test #37:

score: -100
Wrong Answer
time: 495ms
memory: 101584kb

input:

500000 500000
166161 86775 280821 454410 324633 406046 231773 124600 493295 252650 475005 190136 152917 429306 14 453379 201616 66468 175807 107220 20 335544 47285 430095 225595 89234 348072 201728 152312 135619 420827 54567 452444 140915 341932 208819 254154 372448 144955 387131 367708 481790 39018...

output:

0
1279491
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
...

result:

wrong answer 2nd numbers differ - expected: '985', found: '1279491'