QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#787308 | #9743. 重心树 | Godwang | AC ✓ | 44ms | 20288kb | C++23 | 5.6kb | 2024-11-27 11:03:05 | 2024-11-27 11:03:10 |
Judging History
answer
#include <iostream>
using namespace std;
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <stack>
#include <queue>
#include <ctype.h>
#include <vector>
#include <random>
#include<list>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define lowbit(x) ((x)&(-x))
ll extend_gcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
ll fastpow(ll a, ll n, ll mod)
{
ll ans = 1;
a %= mod;
while (n)
{
if (n & 1)
ans = (ans * a) % mod; //% mod
a = (a * a) % mod; //% mod
n >>= 1;
}
return ans;
}
inline void write(__int128 x)
{
if (x > 9)
{
write(x / 10);
}
putchar(x % 10 + '0');
}
__int128 sqrt(__int128 m)
{
__int128 leftt = 0, rightt = ((__int128)1) << 51, ret = -1, mid;
while (leftt < rightt)
{
mid = (leftt + rightt) / 2;
if (mid * mid > m)
{
rightt = mid;
}
else
{
leftt = mid + 1;
ret = mid;
}
}
return ret;
}
const double eps = 1e-6;
int sgn(double x)
{
if(fabs(x)<eps)
{
return 0;
}
else return x<0?-1:1;
}
struct Point
{
double x,y;
Point()
{
}
Point(double x,double y):x(x),y(y)
{
}
Point operator + (Point B)
{
return Point(x+B.x,y+B.y);
}
Point operator - (Point B)
{
return Point(x-B.x,y-B.y);
}
bool operator == (Point B)
{
return sgn(x-B.x)==0&&sgn(y-B.y)==0;
}
bool operator < (Point B)
{
return sgn(x-B.x)<0||(sgn(x-B.x)==0&&sgn(y-B.y)<0);
}
};
typedef Point Vector;
double Cross(Vector A,Vector B)//叉积
{
return A.x*B.y-A.y*B.x;
}
double Distance(Point A,Point B)
{
return hypot(A.x-B.x,A.y-B.y);
}
int Convex_hull(Point *p,int n,Point *ch)
{
n=unique(p,p+n)-p;
sort(p,p+n);
int v=0;
for(int i=0;i<n;i++)
{
while (v>1&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1]))<=0)
{
v--;
}
ch[v++]=p[i];
}
int j=v;
for(int i=n-2;i>=0;i--)
{
while (v>j&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1]))<=0)
{
v--;
}
ch[v++]=p[i];
}
if(n>1)
{
v--;
}
return v;
}
int kmp(string s, string p)
{
int ans = 0, lastt = -1;
int lenp = p.size();
vector<int > Next(lenp+3,0);
rep(i, 1, lenp - 1)
{
int j = Next[i];
while (j && p[j] != p[i])
{
j = Next[j];
}
if (p[j] == p[i])
{
Next[i + 1] = j + 1;
}
else
{
Next[i + 1] = 0;
}
}
int lens = s.size();
int j = 0;
rep(i, 0, lens - 1)
{
while (j && s[i] != p[j])
{
j = Next[j];
}
if (s[i] == p[j])
{
j++;
}
if (j == lenp)
{
ans++;
}
}
return ans;
}
int dir[4][2] =
{
{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 左右上下
// int dir[8][2]={
// {-1, 0}, {0, 1}, {1, 0}, {0, -1},{-1,-1},{-1,1},{1,-1},{1,1}
// };
#define endl '\n'//交互题请删除本行
const ll inf = 1000000000000000000ll;
const ll mod1 = 998244353ll, P1 = 131, mod2 = 1e9 + 7ll, P2 = 13331;
ll inverse(ll x)
{
return fastpow(x,mod1-2,mod1);
}
const int N = 1e6 + 10, M = 1e6 + 10;
///////////////////////////////////
int tt;
int n;
int s[N];
vector<int > v[N];
vector<pii > ans;
///////////////////////////////////
bool cmp(int x,int y)
{
return x>y;
}
int find_set(int x)
{
return x==s[x]?x:s[x]=find_set(s[x]);
}
void merge(int x,int y)
{
int rooty=find_set(y);
if(x==rooty)
{
return;
}
s[rooty]=x;
ans.pb({x,rooty});
}
///////////////////////////////////
void init()
{
ans.clear();
rep(i,1,n)
{
s[i]=i;
}
rep(i,1,n)
{
v[i].clear();
}
}
///////////////////////////////////
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//交互题请删除本行
// freopen("ain.txt", "r", stdin); freopen("aout.txt", "w", stdout);
cin>>tt;
while (tt--)
{
cin>>n;
init();
rep(i,1,n)
{
int num;
cin>>num;
rep(j,1,num)
{
int x;
cin>>x;
v[x].pb(i);
//
// cout<<i<<" "<<x<<endl;
}
}
rep(i,1,n)
{
sort(v[i].begin(),v[i].end(),cmp);
}
per(i,1,n)
{
for(auto j:v[i])
{
//
// cout<<j<<" "<<i<<endl;
merge(j,i);
}
}
for(auto i:ans)
{
cout<<i.first<<" "<<i.second<<endl;
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 5728kb
input:
2 4 2 3 4 1 3 0 0 3 1 3 1 3 0
output:
1 4 2 3 1 2 2 3 1 2
result:
ok Accepted (2 test cases)
Test #2:
score: 0
Accepted
time: 15ms
memory: 5676kb
input:
40000 3 2 2 3 0 0 2 1 2 0 4 2 4 3 1 4 0 0 5 1 3 2 5 4 1 5 0 0 4 3 2 3 4 0 0 0 2 1 2 0 2 1 2 0 5 1 2 3 3 4 5 0 0 0 2 1 2 0 2 1 2 0 5 4 2 3 4 5 0 0 0 0 4 1 2 2 3 4 0 0 5 2 5 4 1 5 1 4 0 0 2 1 2 0 5 1 2 3 3 4 5 0 0 0 5 2 2 3 0 2 4 5 0 0 5 2 5 4 1 5 1 4 0 0 5 2 2 4 2 3 5 0 0 0 4 1 3 1 4 1 4 0 4 2 4 3 1 ...
output:
1 3 1 2 1 2 2 4 1 2 1 3 3 5 2 3 2 4 1 2 1 4 1 3 1 2 1 2 1 2 2 5 2 4 2 3 1 2 1 2 1 2 1 5 1 4 1 3 1 2 2 4 2 3 1 2 2 5 1 2 3 4 1 3 1 2 2 5 2 4 2 3 1 2 3 5 3 4 1 3 1 2 2 5 1 2 3 4 1 3 2 5 1 4 2 3 1 2 3 4 2 3 1 2 2 4 1 2 1 3 2 3 1 2 3 5 1 3 2 4 1 2 1 2 2 3 1 2 3 5 3 4 2 3 1 2 1 2 3 4 2 3 1 2 4 5 2 4 1 2 ...
result:
ok Accepted (40000 test cases)
Test #3:
score: 0
Accepted
time: 8ms
memory: 5680kb
input:
10000 5 2 3 4 1 5 1 5 0 0 4 2 3 4 1 3 0 0 7 1 2 3 4 7 6 1 4 0 1 7 0 0 2 1 2 0 2 1 2 0 8 1 3 1 4 3 4 5 6 2 7 8 0 0 0 0 4 2 2 4 0 1 4 0 4 1 2 2 3 4 0 0 4 1 2 2 3 4 0 0 2 1 2 0 7 3 3 4 6 1 7 1 7 0 1 6 0 0 4 2 4 3 1 4 0 0 3 2 2 3 0 0 6 2 5 4 1 6 1 4 0 1 6 0 3 2 2 3 0 0 5 3 2 5 4 0 1 5 0 0 7 2 4 6 1 5 1 ...
output:
3 5 2 3 1 4 1 2 1 4 2 3 1 2 5 7 2 5 2 6 3 4 2 3 1 2 1 2 1 2 4 8 4 7 3 6 3 5 3 4 2 3 1 2 3 4 1 3 1 2 2 4 2 3 1 2 2 4 2 3 1 2 1 2 3 7 2 3 5 6 1 5 1 4 1 2 2 4 1 2 1 3 1 3 1 2 5 6 2 5 1 2 3 4 1 3 1 3 1 2 3 5 1 3 1 4 1 2 5 7 4 5 1 6 3 4 2 3 1 2 1 2 5 8 3 7 2 3 5 6 2 5 1 2 1 4 2 7 5 6 4 5 2 4 1 2 1 3 5 7 ...
result:
ok Accepted (10000 test cases)
Test #4:
score: 0
Accepted
time: 10ms
memory: 5804kb
input:
10000 10 2 6 7 2 8 4 1 8 0 1 9 1 10 1 9 1 10 0 0 10 3 2 8 5 4 3 9 7 10 0 1 8 0 1 9 0 0 0 0 9 2 2 5 3 3 7 6 0 1 7 2 8 9 0 0 0 0 3 2 2 3 0 0 6 3 4 3 6 1 4 0 0 1 6 0 10 3 2 4 7 2 10 8 1 10 0 1 8 1 9 1 9 0 0 0 3 1 3 1 3 0 5 2 5 4 1 5 1 4 0 0 2 1 2 0 9 3 2 3 7 0 4 5 6 8 9 1 5 0 0 0 0 0 6 4 2 3 4 6 0 0 0 ...
output:
8 10 6 8 7 9 5 7 3 6 2 3 1 5 1 2 2 4 2 10 6 9 2 6 4 8 1 4 2 7 1 5 2 3 1 2 5 9 5 8 4 7 2 4 2 6 1 5 2 3 1 2 1 3 1 2 5 6 1 5 2 4 1 2 1 3 3 10 2 3 7 9 6 7 5 8 2 5 1 6 1 4 1 2 2 3 1 2 2 5 1 2 3 4 1 3 1 2 3 9 3 8 1 7 3 6 4 5 3 4 1 3 1 2 5 6 1 5 1 4 1 3 1 2 3 9 1 3 6 8 5 6 5 7 4 5 1 4 1 2 1 2 6 7 3 6 1 3 3...
result:
ok Accepted (10000 test cases)
Test #5:
score: 0
Accepted
time: 2ms
memory: 5716kb
input:
16 392 4 2 3 165 13 0 2 4 12 0 4 177 7 9 23 2 187 16 0 1 13 0 1 13 2 208 27 0 2 14 22 0 1 23 2 19 20 1 208 3 21 25 27 0 0 0 0 0 2 208 29 0 2 32 31 3 44 40 38 1 208 0 1 44 0 3 35 49 52 1 42 2 36 208 0 0 1 44 1 42 1 49 1 60 2 79 213 0 3 46 79 57 2 47 48 1 60 0 0 0 0 1 213 1 79 1 64 1 57 2 79 63 2 62 2...
output:
383 392 377 383 389 391 386 389 382 390 379 382 378 386 373 378 384 388 377 384 385 387 380 385 372 373 377 380 370 379 364 370 376 381 371 376 364 372 367 377 364 367 361 371 353 361 373 375 367 374 349 353 364 369 364 368 358 366 357 365 356 357 362 364 356 362 348 356 340 348 339 340 333 339 329 ...
result:
ok Accepted (16 test cases)
Test #6:
score: 0
Accepted
time: 2ms
memory: 5720kb
input:
4 502 3 3 253 10 3 7 8 13 2 15 18 1 15 2 6 253 0 1 24 0 1 18 0 2 23 20 2 258 21 1 33 2 24 17 1 24 1 20 0 2 25 26 3 27 42 264 0 2 22 31 0 1 33 2 30 34 0 0 0 1 42 2 265 37 0 0 1 45 0 0 2 269 52 2 269 44 0 1 45 1 56 2 51 58 3 43 47 269 2 54 50 0 0 1 60 1 51 0 1 58 2 53 269 0 0 2 61 63 0 1 60 2 278 67 1...
output:
498 502 498 501 497 500 488 497 493 499 492 498 489 492 489 496 493 495 485 494 490 493 488 490 481 489 472 481 489 491 485 488 469 472 479 485 471 479 470 471 477 487 476 486 472 476 464 470 479 484 477 483 475 482 466 475 463 469 470 480 460 464 470 478 469 477 462 466 460 462 464 474 463 473 459 ...
result:
ok Accepted (4 test cases)
Test #7:
score: 0
Accepted
time: 1ms
memory: 5696kb
input:
1 422 2 9 195 1 9 4 5 195 11 8 1 13 1 13 3 212 12 25 2 16 14 0 0 2 18 212 2 19 31 0 0 0 2 22 29 1 27 1 22 0 1 27 3 221 26 30 1 31 0 1 222 2 33 37 2 33 35 0 0 1 222 1 34 0 0 1 40 2 48 49 1 48 0 2 38 229 2 42 41 0 1 56 1 42 0 0 1 50 3 86 47 238 2 86 51 1 86 0 1 56 1 50 0 0 2 238 58 2 94 57 1 238 1 96 ...
output:
419 422 417 419 411 421 412 420 410 412 413 417 410 413 414 418 414 416 414 415 411 414 409 411 405 409 405 410 398 408 403 407 393 403 401 406 391 401 404 405 395 404 392 395 390 392 388 390 380 388 371 380 387 393 380 387 392 402 382 391 377 382 398 400 392 399 397 398 395 397 395 396 362 371 352 ...
result:
ok Accepted (1 test case)
Test #8:
score: 0
Accepted
time: 19ms
memory: 5816kb
input:
100 509 3 21 3 252 1 21 0 2 23 18 3 252 8 25 2 252 14 2 11 26 0 1 18 1 252 0 1 252 1 26 0 1 34 2 42 22 1 28 1 28 2 24 252 1 51 2 72 39 2 30 31 1 72 0 1 34 1 75 1 39 0 1 252 0 0 1 75 1 252 0 4 37 40 266 46 2 38 39 0 0 3 41 44 48 0 0 1 75 1 266 0 1 53 2 59 62 3 49 266 56 0 0 1 266 1 75 1 266 1 60 1 56...
output:
508 509 503 508 503 507 503 506 504 505 496 504 489 496 501 503 500 501 491 500 482 491 494 502 489 494 489 499 488 498 480 488 492 497 492 495 484 493 485 492 475 485 484 490 484 489 482 484 474 480 466 474 484 487 484 486 471 475 479 482 477 479 471 477 481 483 475 481 468 471 465 468 463 465 453 ...
result:
ok Accepted (100 test cases)
Test #9:
score: 0
Accepted
time: 24ms
memory: 7636kb
input:
5 4174 3 9 15 2088 3 3 18 7 0 2 23 12 1 15 2 19 2088 0 1 19 1 23 2 11 2088 3 16 17 21 0 1 20 2 2088 38 0 0 0 2 28 27 1 20 0 0 2 2088 39 1 34 2 30 47 1 30 2 29 2088 0 1 34 0 0 1 39 1 47 1 2088 0 1 39 1 51 2 2088 44 2 42 51 2 46 49 2 55 2088 1 42 0 1 44 0 1 55 0 2 48 52 0 0 2 2088 58 2 59 53 1 63 0 2 ...
output:
4171 4174 4163 4173 4171 4172 4162 4171 4154 4162 4148 4154 4160 4170 4163 4169 4162 4168 4164 4167 4160 4164 4156 4166 4158 4165 4155 4158 4159 4160 4155 4163 4149 4155 4151 4161 4156 4159 4152 4156 4150 4152 4143 4150 4153 4157 4151 4153 4139 4143 4137 4139 4148 4149 4149 4151 4133 4137 4140 4148 ...
result:
ok Accepted (5 test cases)
Test #10:
score: 0
Accepted
time: 25ms
memory: 8004kb
input:
4 32538 4 21 46 18 16255 2 14 22 1 46 1 17 1 18 2 8 50 2 16 11 1 16 1 16255 1 50 0 2 20 22 1 18 1 17 2 16272 33 0 0 2 23 27 1 50 0 2 32 28 2 30 36 0 1 16272 3 26 38 37 0 0 0 1 50 0 1 16272 1 36 2 42 53 1 39 1 50 0 1 39 3 51 44 48 0 1 50 1 16272 1 55 1 62 0 2 16299 78 1 59 1 16299 0 1 59 2 56 67 1 55...
output:
32530 32538 32529 32537 32530 32536 32525 32535 32526 32534 32517 32526 32531 32533 32529 32531 32525 32532 32521 32529 32527 32530 32517 32527 32516 32521 32527 32528 32511 32517 32516 32525 32520 32524 32513 32520 32517 32523 32516 32522 32515 32516 32506 32513 32518 32519 32515 32518 32511 32515 ...
result:
ok Accepted (4 test cases)
Test #11:
score: 0
Accepted
time: 23ms
memory: 8284kb
input:
3 54304 3 7 27151 13 1 7 3 11 8 27158 2 6 11 1 22 2 9 12 0 0 0 1 27158 3 14 17 31 0 2 25 22 2 15 23 0 1 25 0 1 31 1 27158 1 26 2 36 27158 3 27 28 34 0 1 40 1 26 0 0 0 1 36 2 27158 48 1 40 1 34 2 41 27158 0 1 41 0 5 27175 42 45 46 73 1 48 1 27175 0 0 0 2 52 58 1 27175 0 0 2 50 73 2 49 57 0 0 3 54 56 ...
output:
54301 54304 54301 54303 54292 54302 54293 54301 54291 54293 54284 54291 54294 54300 54289 54294 54290 54299 54288 54290 54293 54298 54292 54297 54295 54296 54289 54295 54288 54292 54284 54288 54286 54289 54282 54286 54281 54287 54279 54285 54282 54284 54278 54282 54275 54278 54267 54275 54281 54283 ...
result:
ok Accepted (3 test cases)
Test #12:
score: 0
Accepted
time: 19ms
memory: 8784kb
input:
2 64362 6 2 13 32175 17 6 18 0 3 15 11 23 2 32175 14 1 17 0 1 15 1 11 1 18 2 32175 20 0 2 22 21 1 28 0 0 1 32175 2 22 24 0 1 32175 0 0 2 27 32 2 25 33 0 0 2 31 32175 0 1 33 2 36 40 1 36 1 36 0 0 3 32175 48 42 1 32175 2 37 46 0 1 40 2 56 45 0 1 56 0 3 32182 80 60 3 32182 52 53 0 0 1 80 1 57 2 32192 7...
output:
64354 64362 64355 64361 64354 64355 64351 64360 64350 64359 64350 64358 64351 64357 64348 64356 64341 64348 64345 64354 64337 64345 64346 64353 64346 64352 64342 64351 64342 64350 64339 64349 64339 64341 64338 64347 64345 64346 64328 64337 64320 64328 64319 64320 64312 64319 64342 64344 64341 64343 ...
result:
ok Accepted (2 test cases)
Test #13:
score: 0
Accepted
time: 26ms
memory: 17604kb
input:
1 194798 3 2 3 97357 0 0 3 6 8 97357 1 6 0 2 16 32 1 24 3 97357 14 19 2 97357 13 2 97357 20 1 32 0 0 2 97357 29 2 28 26 1 97357 2 97357 27 0 0 1 29 1 37 1 97357 1 28 2 35 97357 0 0 0 0 1 35 4 33 34 97357 45 1 37 0 0 0 2 38 97357 0 0 3 97357 48 67 1 45 1 50 1 97357 2 97361 47 3 106 97382 59 1 50 1 48...
output:
194793 194798 194792 194793 194792 194797 194787 194796 194781 194787 194794 194795 194792 194794 194786 194792 194785 194786 194776 194785 194784 194791 194789 194790 194781 194789 194784 194788 194767 194776 194761 194767 194778 194784 194768 194778 194759 194768 194779 194783 194770 194779 194773...
result:
ok Accepted (1 test case)
Test #14:
score: 0
Accepted
time: 10ms
memory: 5680kb
input:
10000 8 2 2 5 3 8 6 7 1 5 1 8 0 0 0 0 8 4 3 4 8 7 1 5 1 5 0 0 1 8 0 0 4 2 2 4 0 1 4 0 3 2 2 3 0 0 2 1 2 0 12 1 4 4 3 8 10 6 0 2 7 11 1 10 0 0 2 9 12 0 0 1 12 0 6 2 3 5 2 6 4 1 6 0 0 0 4 1 3 1 4 1 4 0 7 2 3 7 1 5 2 4 6 0 1 6 0 0 14 4 2 13 5 7 2 4 6 1 13 2 8 14 2 9 11 2 10 12 0 0 0 0 0 0 0 0 4 2 4 3 1...
output:
4 8 2 4 2 7 2 6 3 5 1 3 1 2 6 8 1 6 1 7 3 5 2 3 1 4 1 2 3 4 1 3 1 2 1 3 1 2 1 2 11 12 8 11 4 8 5 10 2 5 8 9 2 4 4 7 2 6 1 2 2 3 3 6 2 3 1 5 2 4 1 2 3 4 2 3 1 2 1 7 5 6 3 5 2 3 3 4 1 2 4 14 3 13 1 3 6 12 5 11 6 10 5 9 4 8 1 7 2 6 1 5 2 4 1 2 2 4 1 2 1 3 1 4 2 3 1 2 7 10 5 7 2 9 1 8 4 5 1 4 2 6 2 3 1 ...
result:
ok Accepted (10000 test cases)
Test #15:
score: 0
Accepted
time: 15ms
memory: 5736kb
input:
10000 14 2 2 10 4 6 4 5 12 1 6 2 7 9 2 11 13 0 0 1 14 0 1 14 0 0 0 0 11 4 4 5 6 11 2 7 10 1 5 2 8 9 0 0 1 8 0 0 0 0 9 4 3 4 6 7 1 8 2 5 9 0 0 0 0 1 9 0 16 2 8 7 2 12 8 1 12 1 8 1 7 1 13 0 4 9 10 15 16 0 0 1 15 1 13 0 1 16 0 0 10 3 4 3 7 2 10 5 0 1 10 0 1 7 2 8 9 0 0 0 5 3 5 3 4 1 5 0 0 0 7 2 3 5 2 3...
output:
10 14 8 10 5 13 2 12 5 11 1 8 4 9 4 7 3 6 2 3 2 5 2 4 1 2 1 11 2 10 4 9 7 8 4 7 2 4 1 6 3 5 1 3 1 2 8 9 3 8 2 3 1 7 1 6 3 5 1 4 1 2 14 16 8 14 11 15 8 11 12 13 6 12 3 6 2 3 8 10 8 9 4 8 2 4 1 2 5 7 1 5 4 10 2 4 7 9 7 8 6 7 1 6 2 5 1 2 1 3 2 5 1 2 1 4 1 3 3 7 2 6 1 5 3 4 2 3 1 2 1 10 6 9 1 6 7 8 4 7 ...
result:
ok Accepted (10000 test cases)
Test #16:
score: 0
Accepted
time: 17ms
memory: 5688kb
input:
10000 17 2 2 12 4 14 6 11 10 2 7 12 1 14 1 6 0 0 2 15 13 1 12 0 1 15 2 16 17 0 0 0 0 0 9 3 5 4 9 1 5 1 4 0 2 7 8 1 9 0 0 0 5 2 3 5 1 4 1 4 0 0 18 3 4 3 10 2 9 16 0 2 14 12 3 8 15 11 1 18 1 14 0 1 13 1 17 0 1 13 0 0 1 17 1 18 0 0 2 1 2 0 14 3 3 13 7 2 6 11 1 10 1 13 2 8 14 1 10 1 12 1 12 1 14 0 0 0 0...
output:
12 17 12 16 11 15 8 11 4 14 2 4 8 13 9 12 3 9 1 3 2 8 2 10 3 7 5 6 2 5 1 2 6 9 1 6 5 8 5 7 2 5 1 2 3 4 1 3 1 5 3 4 2 3 1 2 16 18 6 16 15 17 10 15 2 6 5 10 7 14 4 7 12 13 9 12 4 9 5 11 1 5 2 4 5 8 1 2 1 3 1 2 9 14 5 9 4 13 1 4 8 12 7 8 2 11 6 10 3 6 5 7 1 5 2 3 1 2 1 11 2 10 5 9 1 5 2 8 6 7 3 6 2 3 2...
result:
ok Accepted (10000 test cases)
Test #17:
score: 0
Accepted
time: 19ms
memory: 5584kb
input:
10000 12 3 3 6 11 2 9 7 1 9 1 12 1 7 1 12 0 1 10 1 10 0 0 0 9 4 7 5 6 9 1 7 1 8 1 5 0 0 1 8 0 0 16 3 5 3 6 3 4 7 12 0 0 2 7 11 0 3 9 15 13 1 11 0 1 15 0 2 14 16 0 0 0 0 13 1 3 3 4 8 10 4 6 7 9 12 2 5 6 0 2 11 13 0 0 0 0 0 0 0 4 2 4 3 1 4 0 0 8 2 5 3 2 6 7 0 1 6 1 8 1 8 0 0 20 2 7 6 3 4 10 11 2 13 8 ...
output:
6 12 4 6 1 11 9 10 8 9 3 8 2 3 5 7 2 5 1 4 1 2 1 9 7 8 3 7 2 3 1 2 1 6 4 5 1 4 12 16 10 15 7 10 12 14 7 13 2 12 8 11 5 8 7 9 5 7 2 5 1 6 1 2 2 4 1 3 6 13 3 12 6 11 2 10 3 9 2 8 3 7 4 6 3 4 4 5 2 3 1 2 2 4 1 2 1 3 6 8 5 6 2 7 4 5 2 4 1 2 1 3 10 20 11 19 17 18 10 17 13 16 6 13 11 15 4 14 3 6 10 12 2 1...
result:
ok Accepted (10000 test cases)
Test #18:
score: 0
Accepted
time: 21ms
memory: 5624kb
input:
100000 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 2...
output:
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
result:
ok Accepted (100000 test cases)
Test #19:
score: 0
Accepted
time: 37ms
memory: 15836kb
input:
1 200000 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 66869 1 6...
output:
247 200000 303 199999 199997 199998 378 199997 399 199996 421 199995 423 199994 425 199993 445 199992 449 199991 450 199990 467 199989 199987 199988 473 199987 475 199986 199984 199985 485 199984 199982 199983 497 199982 516 199981 199979 199980 518 199979 538 199978 545 199977 199975 199976 545 199...
result:
ok Accepted (1 test case)
Test #20:
score: 0
Accepted
time: 36ms
memory: 20288kb
input:
1 200000 5703 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 1374 1375 1440 1486 1487 1488 1489 1845 1846 1847 1848 1849 1850 1851 1860 1861 1862 1863 1864 1865 1866 1867 1868 1888 1889 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3446 ...
output:
199907 200000 199907 199999 199907 199998 199907 199997 199907 199996 199907 199995 199907 199994 199907 199993 199907 199992 199907 199991 199907 199990 199907 199989 199907 199988 199907 199987 199907 199986 199907 199985 199907 199984 199907 199983 199907 199982 199907 199981 199907 199980 199907...
result:
ok Accepted (1 test case)
Test #21:
score: 0
Accepted
time: 44ms
memory: 16592kb
input:
1 200000 11 39 63012 63019 63148 63219 63220 63262 63263 130152 198563 199731 9 3 4 39 60342 60876 60977 62603 62911 62944 0 5 5 7 23 25 36 0 3 8 19 22 4 8 15 16 18 4 9 10 12 14 0 0 1 13 1 13 0 0 0 0 1 18 0 2 20 21 0 0 0 0 2 27 31 2 26 29 0 2 28 30 0 1 30 0 3 32 33 35 0 0 1 35 0 2 37 38 0 0 15 41 42...
output:
199999 200000 199997 199999 199957 199997 199997 199998 199994 199996 199994 199995 199957 199994 199957 199993 199991 199992 199957 199991 199977 199990 199988 199989 199977 199988 199977 199987 199985 199986 199977 199985 199977 199984 199978 199983 199980 199982 199980 199981 199979 199980 199978...
result:
ok Accepted (1 test case)
Test #22:
score: 0
Accepted
time: 34ms
memory: 13124kb
input:
2 100000 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 18907 1 1...
output:
165 100000 204 99999 254 99998 255 99997 255 99996 263 99995 290 99994 99992 99993 290 99992 305 99991 307 99990 321 99989 336 99988 99986 99987 99985 99986 343 99985 357 99984 99982 99983 99981 99982 376 99981 99979 99980 378 99979 387 99978 99976 99977 393 99976 414 99975 414 99974 418 99973 433 9...
result:
ok Accepted (2 test cases)
Test #23:
score: 0
Accepted
time: 30ms
memory: 13788kb
input:
2 100000 2810 2 3 4 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 951 952 953 1008 1009 1010 1019 1020 1021 1046 1047 1048 1049 1050 1581 1582 1583 1584 1585 1586 1587 1588 1589 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1680 1693 1694 1711 1712 1713 1732 1733 1951 1952 2040 20...
output:
1 100000 99815 99999 99815 99998 99815 99997 99815 99996 99815 99995 99815 99994 99815 99993 99815 99992 99815 99991 99815 99990 99815 99989 99815 99988 99815 99987 99815 99986 99815 99985 99815 99984 99815 99983 99815 99982 99815 99981 99815 99980 99815 99979 99815 99978 99815 99977 99815 99976 998...
result:
ok Accepted (2 test cases)
Extra Test:
score: 0
Extra Test Passed