QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189909 | #1190. Twin Trees Bros | KKT89 | AC ✓ | 87ms | 4340kb | C++17 | 5.2kb | 2023-09-28 01:27:27 | 2023-09-28 01:27:27 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <assert.h>
using namespace std;
const double eps = 1e-8;
int sgn(double a){return a<-eps?-1:a>eps?1:0;}
int sgn(double a, double b){return sgn(a-b);}
struct point{
double x,y,z;
point() {}
point(double x,double y,double z): x(x), y(y), z(z) {}
point operator+ (const point& p){
return point(x+p.x, y+p.y, z+p.z);
}
point operator- (const point& p){
return point(x-p.x, y-p.y, z-p.z);
}
point operator/ (const double d){
return point(x/d, y/d, z/d);
}
double dist(const point& p){
return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y) + (z-p.z)*(z-p.z));
}
};
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
// input
int n; cin >> n;
vector<point> A(n);
for(int i=0;i<n;i++){
int x,y,z; cin >> x >> y >> z;
A[i] = point(x,y,z);
}
vector<vector<int>> g1(n);
for(int i=1;i<n;i++){
int x,y; cin >> x >> y;
x--; y--;
g1[x].push_back(y);
g1[y].push_back(x);
}
vector<point> B(n);
for(int i=0;i<n;i++){
int x,y,z; cin >> x >> y >> z;
B[i] = point(x,y,z);
}
vector<vector<int>> g2(n);
for(int i=1;i<n;i++){
int x,y; cin >> x >> y;
x -= n+1; y -= n+1;
g2[x].push_back(y);
g2[y].push_back(x);
}
// 木の葉ノードを基準に変形
auto getTree = [&](vector<point> A, vector<vector<int>> &g, int leaf, int idx = -1)->vector<point>{
// step1: 葉ノードを原点に平行移動させる
{
auto p = A[leaf];
for(int i=0;i<n;i++){
A[i] = A[i]-p;
}
}
// step2: 葉ノードと親の距離を1にする
int par = g[leaf][0];
{
double d = A[leaf].dist(A[par]);
vector<point> nA(n);
nA[leaf] = A[leaf];
auto dfs = [&](auto self, int s, int p)->void{
for(int t:g1[s]){
if(t == p) continue;
point v = (A[t]-A[s])/d;
nA[t] = nA[s]+v;
self(self, t, s);
}
};
dfs(dfs, leaf, -1);
swap(A, nA);
}
// step3:z軸中心に回転させ、親ノードをxz平面上へ
{
double theta = -atan2(A[par].y, A[par].x);
for(int i=0;i<n;i++){
double nx = A[i].x*cos(theta) - A[i].y*sin(theta);
double ny = A[i].x*sin(theta) + A[i].y*cos(theta);
A[i].x = nx, A[i].y = ny;
}
}
// step4:y軸中心に回転させ、親ノードをx軸上へ
{
double theta = -atan2(A[par].z, A[par].x);
for(int i=0;i<n;i++){
double nx = A[i].x*cos(theta) - A[i].z*sin(theta);
double nz = A[i].x*sin(theta) + A[i].z*cos(theta);
A[i].x = nx, A[i].z = nz;
}
}
// step5:x軸中心に回転させ、親ノードに接続する元の葉以外をy軸上へ
// idx = -1 ならば任意、それ以外はA[idx]を合わせる
if(idx == -1){
for(int t:g[par]){
if(t == leaf) continue;
if(abs(A[t].y) < eps and abs(A[t].z) < eps) continue;
idx = t; break;
}
}
if(idx != -1){
double theta = -atan2(A[idx].z, A[idx].y);
for(int i=0;i<n;i++){
double ny = A[i].y*cos(theta) - A[i].z*sin(theta);
double nz = A[i].y*sin(theta) + A[i].z*cos(theta);
A[i].y = ny, A[i].z = nz;
}
}
return A;
};
int lA = -1;
for(int i=0;i<n;i++){
sort(g1[i].begin(), g1[i].end());
if(g1[i].size() == 1) lA = i;
}
assert(lA != -1);
auto gA = getTree(A, g1, lA);
// 比較用の関数
set<vector<int>> st;
auto compare = [&](vector<point> &A, vector<point> &B)->void{
vector<int> Bidx(n,-1),Binv(n);
// A[i] = B[Bidx[i]]
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(sgn(A[i].x, B[j].x) or sgn(A[i].y, B[j].y) or sgn(A[i].z, B[j].z)) continue;
Bidx[i] = j; Binv[j] = i; break;
}
if(Bidx[i] == -1) return;
}
// 隣接リストがそれぞれ一致しているか調べる
for(int i=0;i<n;i++){
auto v = g1[i], vv = g2[Bidx[i]];
for(int &j:vv){
j = Binv[j];
}
sort(vv.begin(), vv.end());
if(v != vv) return;
}
st.insert(Bidx);
};
// AとBの比較
for(int i=0;i<n;i++){
if(g2[i].size() != 1) continue;
// iは葉ノード
int par = g2[i][0];
// step5でy軸に合わせるidxを全て試す
for(int j:g2[par]){
auto gB = getTree(B, g2, i, (i==j?-1:j));
compare(gA, gB);
}
}
// output
cout << st.size() << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4036kb
input:
3 0 0 0 1 0 0 3 0 0 1 2 2 3 0 0 0 0 2 2 0 3 3 4 5 5 6
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4236kb
input:
4 1 0 0 2 0 0 2 1 0 2 -1 0 1 2 2 3 2 4 0 1 1 0 0 0 0 2 0 0 0 2 5 6 5 7 5 8
output:
2
result:
ok answer is '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
3 0 0 0 1 0 0 3 0 0 1 2 2 3 0 0 0 0 2 2 0 3 3 4 5 5 6
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4224kb
input:
7 5 3 1 5 5 3 5 1 -1 7 5 3 3 5 3 7 1 -1 3 1 -1 1 2 1 3 1 4 1 5 1 6 1 7 13 23 24 10 20 30 10 20 36 10 20 24 13 23 36 7 17 36 7 17 24 8 9 9 10 9 11 9 12 9 13 9 14
output:
4
result:
ok answer is '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
7 5 3 1 5 5 3 5 1 -1 7 5 3 3 5 3 7 1 -1 3 1 -1 1 2 1 3 1 4 1 5 1 6 1 7 13 23 24 13 23 36 10 20 30 10 20 36 10 20 24 7 17 36 7 17 24 8 9 9 10 10 11 10 12 10 13 10 14
output:
0
result:
ok answer is '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
7 5 3 1 5 5 3 5 1 -1 7 5 3 3 5 3 7 1 -1 3 1 -1 1 2 1 3 1 4 1 5 1 6 1 7 13 23 24 10 20 30 10 20 36 10 20 24 13 23 37 7 17 36 7 17 24 8 9 9 10 9 11 9 12 9 13 9 14
output:
0
result:
ok answer is '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4228kb
input:
9 134 234 164 185 285 198 134 234 232 185 285 266 134 234 300 185 285 334 134 234 368 185 285 402 134 234 436 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 50 30 278 184 164 680 -84 -104 680 318 298 278 -218 -238 278 452 432 680 -352 -372 680 586 566 278 -486 -506 278 10 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18
output:
2
result:
ok answer is '2'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4212kb
input:
9 185 285 198 134 234 436 185 285 266 185 285 402 134 234 232 134 234 300 134 234 368 134 234 164 185 285 334 1 8 1 5 2 4 3 5 3 6 4 7 6 9 7 9 318 298 278 452 432 680 184 164 680 -218 -238 278 -352 -372 680 586 566 278 -486 -506 278 -84 -104 680 50 30 278 10 12 10 11 11 15 12 18 13 17 13 14 14 16 17 18
output:
2
result:
ok answer is '2'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
9 185 285 198 134 234 436 185 285 266 185 285 402 134 234 232 134 234 300 134 234 368 134 234 164 185 285 334 1 8 1 5 2 6 3 5 3 6 4 7 6 9 7 9 318 298 278 452 432 680 184 164 680 -218 -238 278 -352 -372 680 586 566 278 -486 -506 278 -84 -104 680 50 30 278 10 12 10 11 11 15 12 18 13 17 13 14 14 16 17 18
output:
0
result:
ok answer is '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4232kb
input:
9 185 285 198 134 235 436 185 285 266 185 285 402 134 234 232 134 234 300 134 234 368 134 234 164 185 285 334 1 8 1 5 2 4 3 5 3 6 4 7 6 9 7 9 318 298 278 452 432 680 184 164 680 -218 -238 278 -352 -372 680 586 566 278 -486 -506 278 -84 -104 680 50 30 278 10 12 10 11 11 15 12 18 13 17 13 14 14 16 17 18
output:
0
result:
ok answer is '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 4076kb
input:
7 -220 520 720 60 240 440 200 100 300 620 -320 -120 -80 380 580 480 -180 20 340 -40 160 1 3 1 7 1 6 1 4 2 3 3 5 230 210 370 50 30 10 170 150 250 -10 -30 -110 -130 -150 -350 110 90 130 -70 -90 -230 8 11 8 9 8 14 8 12 9 10 9 13
output:
1
result:
ok answer is '1'
Test #12:
score: 0
Accepted
time: 0ms
memory: 4220kb
input:
7 -220 520 720 60 240 440 200 100 300 620 -320 -120 -80 380 580 480 -180 20 340 -40 160 1 3 1 7 1 6 2 3 3 5 4 5 230 210 370 50 30 10 170 150 250 -10 -30 -110 -130 -150 -350 110 90 130 -70 -90 -230 8 11 8 9 8 14 8 12 9 10 9 13
output:
0
result:
ok answer is '0'
Test #13:
score: 0
Accepted
time: 0ms
memory: 4148kb
input:
7 -220 520 720 60 240 440 200 100 300 620 -320 -120 -80 380 580 480 -180 20 341 -40 161 1 3 1 7 1 6 1 4 2 3 3 5 230 210 370 50 30 10 170 150 250 -10 -30 -110 -130 -150 -350 110 90 130 -70 -90 -230 8 11 8 9 8 14 8 12 9 10 9 13
output:
0
result:
ok answer is '0'
Test #14:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
12 -356 -256 92 -356 -256 -12 -356 -256 612 -252 -152 612 -252 -152 508 -252 -152 92 -356 -256 508 -252 -152 196 -252 -152 -12 -252 -152 404 -356 -256 404 -356 -256 196 1 4 2 4 3 11 4 5 4 12 5 11 6 12 7 11 8 12 9 12 10 11 602 582 194 234 214 562 418 398 562 -134 -154 562 234 214 194 -134 -154 194 -3...
output:
1
result:
ok answer is '1'
Test #15:
score: 0
Accepted
time: 0ms
memory: 4220kb
input:
12 -356 -256 92 -356 -256 -12 -356 -256 612 -252 -152 612 -252 -152 508 -252 -152 92 -356 -256 508 -252 -152 196 -252 -152 -12 -252 -152 404 -356 -256 404 -356 -256 196 1 4 2 4 3 11 4 5 4 12 5 11 6 7 7 11 8 12 9 12 10 11 602 582 194 234 214 562 418 398 562 -134 -154 562 234 214 194 -134 -154 194 -31...
output:
0
result:
ok answer is '0'
Test #16:
score: 0
Accepted
time: 0ms
memory: 4220kb
input:
12 -356 -256 92 -356 -256 -12 -356 -256 612 -252 -152 612 -252 -152 508 -252 -152 93 -356 -256 508 -252 -152 196 -252 -152 -12 -252 -152 404 -356 -256 404 -356 -256 196 1 4 2 4 3 11 4 5 4 12 5 11 6 12 7 11 8 12 9 12 10 11 418 398 562 -502 -522 562 -134 -154 194 234 214 562 -502 -522 194 602 582 562 ...
output:
0
result:
ok answer is '0'
Test #17:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
4 -500 -400 360 -500 -400 240 100 200 240 100 200 360 1 2 2 4 3 4 890 114 94 -790 114 94 890 -54 -74 -790 -54 -74 5 8 5 7 6 8
output:
2
result:
ok answer is '2'
Test #18:
score: 0
Accepted
time: 0ms
memory: 4100kb
input:
4 -500 -400 360 -500 -400 240 100 200 240 100 200 360 1 2 2 4 3 4 890 114 94 890 -54 -74 -790 114 94 -790 -54 -74 5 8 6 7 7 8
output:
0
result:
ok answer is '0'
Test #19:
score: 0
Accepted
time: 0ms
memory: 4144kb
input:
4 -500 -400 360 -500 -400 240 100 200 240 100 200 360 1 2 2 4 3 4 -790 114 94 890 -54 -75 890 114 94 -790 -54 -74 5 8 6 7 7 8
output:
0
result:
ok answer is '0'
Test #20:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
4 1 0 0 2 0 0 2 1 0 2 -1 0 1 2 2 3 2 4 0 1 1 0 0 0 0 2 0 0 0 2 5 6 5 7 5 8
output:
2
result:
ok answer is '2'
Test #21:
score: 0
Accepted
time: 2ms
memory: 4076kb
input:
199 -175 -10 195 -95 -125 390 -110 25 310 -105 -170 360 -145 -60 205 -340 -75 315 -305 -10 275 -245 -5 230 -175 5 390 -295 -40 230 -235 -90 205 -290 -225 310 -130 -5 360 -105 -45 260 -95 -190 275 -105 -30 345 -240 -5 355 -90 -15 365 -295 -155 260 -285 -165 410 -245 -195 370 -225 -115 160 -235 -195 2...
output:
24
result:
ok answer is '24'
Test #22:
score: 0
Accepted
time: 2ms
memory: 4268kb
input:
199 -175 -10 195 -95 -125 390 -110 25 310 -105 -170 360 -145 -60 205 -340 -75 315 -305 -10 275 -245 -5 230 -175 5 390 -295 -40 230 -235 -90 205 -290 -225 310 -130 -5 360 -105 -45 260 -95 -190 275 -105 -30 345 -240 -5 355 -90 -15 365 -295 -155 260 -285 -165 410 -245 -195 370 -225 -115 160 -235 -195 2...
output:
0
result:
ok answer is '0'
Test #23:
score: 0
Accepted
time: 2ms
memory: 4280kb
input:
199 -175 -10 195 -95 -125 390 -110 25 310 -105 -170 360 -145 -60 205 -340 -75 315 -305 -10 275 -245 -5 230 -175 5 390 -295 -40 230 -235 -90 205 -290 -225 310 -130 -5 360 -105 -45 260 -95 -190 275 -105 -30 345 -240 -5 355 -90 -15 365 -295 -155 260 -285 -165 410 -245 -195 370 -225 -115 160 -235 -195 2...
output:
0
result:
ok answer is '0'
Test #24:
score: 0
Accepted
time: 1ms
memory: 4080kb
input:
165 -170 -94 357 -221 -121 384 -191 -55 294 -143 -139 309 -158 -106 351 -161 -184 267 -146 -178 282 -209 -43 339 -158 -181 264 -149 -157 285 -179 -184 321 -215 -151 357 -209 -55 306 -239 -16 267 -185 -43 249 -221 -16 321 -209 -145 294 -233 -16 339 -248 -148 213 -194 -70 243 -242 -19 264 -179 -16 279...
output:
8
result:
ok answer is '8'
Test #25:
score: 0
Accepted
time: 1ms
memory: 4272kb
input:
165 -170 -94 357 -221 -121 384 -191 -55 294 -143 -139 309 -158 -106 351 -161 -184 267 -146 -178 282 -209 -43 339 -158 -181 264 -149 -157 285 -179 -184 321 -215 -151 357 -209 -55 306 -239 -16 267 -185 -43 249 -221 -16 321 -209 -145 294 -233 -16 339 -248 -148 213 -194 -70 243 -242 -19 264 -179 -16 279...
output:
0
result:
ok answer is '0'
Test #26:
score: 0
Accepted
time: 1ms
memory: 4052kb
input:
165 -170 -94 357 -221 -121 384 -191 -55 294 -143 -139 309 -158 -106 351 -161 -184 267 -146 -178 282 -209 -43 339 -158 -181 264 -149 -157 285 -179 -184 321 -215 -151 357 -209 -55 306 -239 -16 267 -185 -43 249 -221 -16 321 -209 -145 294 -233 -16 339 -248 -148 213 -194 -70 243 -242 -19 264 -179 -16 279...
output:
0
result:
ok answer is '0'
Test #27:
score: 0
Accepted
time: 1ms
memory: 4320kb
input:
165 -248 -58 384 -221 -139 261 -239 -121 261 -116 -58 348 -239 -88 234 -239 -106 345 -125 -151 279 -230 -121 339 -146 -55 285 -149 -109 249 -221 -61 339 -179 -49 225 -239 -115 333 -254 -85 255 -239 -133 285 -284 -148 258 -167 -115 339 -251 -49 291 -170 -121 261 -248 -142 216 -245 -94 339 -266 -112 2...
output:
4
result:
ok answer is '4'
Test #28:
score: 0
Accepted
time: 1ms
memory: 4280kb
input:
165 -248 -58 384 -221 -139 261 -239 -121 261 -116 -58 348 -239 -88 234 -239 -106 345 -125 -151 279 -230 -121 339 -146 -55 285 -149 -109 249 -221 -61 339 -179 -49 225 -239 -115 333 -254 -85 255 -239 -133 285 -284 -148 258 -167 -115 339 -251 -49 291 -170 -121 261 -248 -142 216 -245 -94 339 -266 -112 2...
output:
0
result:
ok answer is '0'
Test #29:
score: 0
Accepted
time: 1ms
memory: 4280kb
input:
165 -248 -58 384 -221 -139 261 -239 -121 261 -116 -58 348 -239 -88 234 -239 -106 345 -125 -151 279 -230 -121 339 -146 -55 285 -149 -109 249 -221 -61 339 -179 -49 225 -239 -115 333 -254 -85 255 -239 -133 285 -284 -148 258 -167 -115 339 -251 -49 291 -170 -121 261 -248 -142 216 -245 -94 339 -266 -112 2...
output:
0
result:
ok answer is '0'
Test #30:
score: 0
Accepted
time: 1ms
memory: 4304kb
input:
67 -39 -16 321 -277 -142 307 -39 -121 384 -396 -30 405 -312 -219 272 -4 -30 195 -361 -16 279 -270 -100 300 -305 5 328 -95 5 272 -361 -121 216 -95 -128 195 -88 19 272 -396 -170 195 -116 -184 412 -361 -79 384 -88 -79 384 -95 -72 405 -116 -16 188 -130 -100 300 -361 -184 321 -312 19 328 -312 -184 279 -4...
output:
8
result:
ok answer is '8'
Test #31:
score: 0
Accepted
time: 1ms
memory: 4164kb
input:
67 -39 -16 321 -277 -142 307 -39 -121 384 -396 -30 405 -312 -219 272 -4 -30 195 -361 -16 279 -270 -100 300 -305 5 328 -95 5 272 -361 -121 216 -95 -128 195 -88 19 272 -396 -170 195 -116 -184 412 -361 -79 384 -88 -79 384 -95 -72 405 -116 -16 188 -130 -100 300 -361 -184 321 -312 19 328 -312 -184 279 -4...
output:
0
result:
ok answer is '0'
Test #32:
score: 0
Accepted
time: 0ms
memory: 4232kb
input:
67 -39 -16 321 -277 -142 307 -39 -121 384 -396 -30 405 -312 -219 272 -4 -30 195 -361 -16 279 -270 -100 300 -305 5 328 -95 5 272 -361 -121 216 -95 -128 195 -88 19 272 -396 -170 195 -116 -184 412 -361 -79 384 -88 -79 384 -95 -72 405 -116 -16 188 -130 -100 300 -361 -184 321 -312 19 328 -312 -184 279 -4...
output:
0
result:
ok answer is '0'
Test #33:
score: 0
Accepted
time: 0ms
memory: 4120kb
input:
83 -81 -51 125 -242 -191 181 -123 -128 391 -109 -219 125 -326 -198 503 -81 -191 475 -277 -79 146 -144 26 426 -291 -142 419 -109 -58 419 -165 -191 97 -109 -135 503 -123 -121 146 -81 -149 475 -277 -121 454 -193 -135 216 -81 -9 125 -193 -65 384 -249 19 125 -109 -65 97 -291 -219 475 -235 -191 503 -123 -...
output:
2
result:
ok answer is '2'
Test #34:
score: 0
Accepted
time: 0ms
memory: 4168kb
input:
83 -81 -51 125 -242 -191 181 -123 -128 391 -109 -219 125 -326 -198 503 -81 -191 475 -277 -79 146 -144 26 426 -291 -142 419 -109 -58 419 -165 -191 97 -109 -135 503 -123 -121 146 -81 -149 475 -277 -121 454 -193 -135 216 -81 -9 125 -193 -65 384 -249 19 125 -109 -65 97 -291 -219 475 -235 -191 503 -123 -...
output:
0
result:
ok answer is '0'
Test #35:
score: 0
Accepted
time: 1ms
memory: 4016kb
input:
83 -81 -51 125 -242 -191 181 -123 -128 391 -109 -219 125 -326 -198 503 -81 -191 475 -277 -79 146 -144 26 426 -291 -142 419 -109 -58 419 -165 -191 97 -109 -135 503 -123 -121 146 -81 -149 475 -277 -121 454 -193 -135 216 -81 -9 125 -193 -65 384 -249 19 125 -109 -65 97 -291 -219 475 -235 -191 503 -123 -...
output:
0
result:
ok answer is '0'
Test #36:
score: 0
Accepted
time: 1ms
memory: 4020kb
input:
83 -102 -142 321 -81 -156 167 -298 -142 279 -102 -163 174 3 -65 174 -326 -44 195 -123 -198 216 -291 19 286 -109 -114 419 -81 33 244 3 -226 265 -354 -16 265 -123 -2 384 -403 -135 174 -277 -16 398 -74 -156 195 3 26 335 -319 -233 244 -277 -198 384 -81 -44 433 -102 26 237 -74 -205 356 -46 -121 321 -291 ...
output:
2
result:
ok answer is '2'
Test #37:
score: 0
Accepted
time: 1ms
memory: 4056kb
input:
83 -102 -142 321 -81 -156 167 -298 -142 279 -102 -163 174 3 -65 174 -326 -44 195 -123 -198 216 -291 19 286 -109 -114 419 -81 33 244 3 -226 265 -354 -16 265 -123 -2 384 -403 -135 174 -277 -16 398 -74 -156 195 3 26 335 -319 -233 244 -277 -198 384 -81 -44 433 -102 26 237 -74 -205 356 -46 -121 321 -291 ...
output:
0
result:
ok answer is '0'
Test #38:
score: 0
Accepted
time: 1ms
memory: 4236kb
input:
83 -102 -142 321 -81 -156 167 -298 -142 279 -102 -163 174 3 -65 174 -326 -44 195 -123 -198 216 -291 19 286 -109 -114 419 -81 33 244 3 -226 265 -354 -16 265 -123 -2 384 -403 -135 174 -277 -16 398 -74 -156 195 3 26 335 -319 -233 244 -277 -198 384 -81 -44 433 -102 26 237 -74 -205 356 -46 -121 321 -291 ...
output:
0
result:
ok answer is '0'
Test #39:
score: 0
Accepted
time: 1ms
memory: 4232kb
input:
83 -92 50 106 -4 82 -34 96 -70 66 92 -82 -14 56 50 102 40 -26 82 -8 66 10 24 -70 98 44 82 46 92 62 74 52 50 -46 24 58 90 -40 66 18 52 -70 -22 -64 102 -42 32 50 14 -80 62 82 24 -78 -30 56 10 18 -84 82 14 40 42 46 32 62 90 24 102 102 -52 98 -22 48 14 102 40 62 -22 -4 50 82 16 106 -30 -88 34 90 20 -10 ...
output:
2
result:
ok answer is '2'
Test #40:
score: 0
Accepted
time: 1ms
memory: 4092kb
input:
83 -92 50 106 -4 82 -34 96 -70 66 92 -82 -14 56 50 102 40 -26 82 -8 66 10 24 -70 98 44 82 46 92 62 74 52 50 -46 24 58 90 -40 66 18 52 -70 -22 -64 102 -42 32 50 14 -80 62 82 24 -78 -30 56 10 18 -84 82 14 40 42 46 32 62 90 24 102 102 -52 98 -22 48 14 102 40 62 -22 -4 50 82 16 106 -30 -88 34 90 20 -10 ...
output:
0
result:
ok answer is '0'
Test #41:
score: 0
Accepted
time: 1ms
memory: 3984kb
input:
83 -92 50 106 -4 82 -34 96 -70 66 92 -82 -14 56 50 102 40 -26 82 -8 66 10 24 -70 98 44 82 46 92 62 74 52 50 -46 24 58 90 -40 66 18 52 -70 -22 -64 102 -42 32 50 14 -80 62 82 24 -78 -30 56 10 18 -84 82 14 40 42 46 32 62 90 24 102 102 -52 98 -22 48 14 102 40 62 -22 -4 50 82 16 106 -30 -88 34 90 20 -10 ...
output:
0
result:
ok answer is '0'
Test #42:
score: 0
Accepted
time: 2ms
memory: 4124kb
input:
200 139 5 8 -17 5 8 231 5 8 135 5 8 -201 5 8 -377 5 8 79 5 8 123 5 8 235 5 8 -57 5 8 -225 5 8 -361 5 8 -161 5 8 -373 5 8 -129 5 8 23 5 8 -177 5 8 -65 5 8 -77 5 8 -353 5 8 267 5 8 -69 5 8 147 5 8 227 5 8 351 5 8 -305 5 8 -1 5 8 -165 5 8 55 5 8 -257 5 8 263 5 8 -121 5 8 -221 5 8 -249 5 8 159 5 8 67 5 ...
output:
1
result:
ok answer is '1'
Test #43:
score: 0
Accepted
time: 1ms
memory: 4284kb
input:
200 139 5 8 -17 5 8 231 5 8 135 5 8 -201 5 8 -377 5 8 79 5 8 123 5 8 235 5 8 -57 5 8 -225 5 8 -361 5 8 -161 5 8 -373 5 8 -129 5 8 23 5 8 -177 5 8 -65 5 8 -77 5 8 -353 5 8 267 5 8 -69 5 8 147 5 8 227 5 8 351 5 8 -305 5 8 -1 5 8 -165 5 8 55 5 8 -257 5 8 263 5 8 -121 5 8 -221 5 8 -249 5 8 159 5 8 67 5 ...
output:
0
result:
ok answer is '0'
Test #44:
score: 0
Accepted
time: 0ms
memory: 4268kb
input:
200 139 5 8 -17 5 8 231 5 8 135 5 8 -201 5 8 -377 5 8 79 5 8 123 5 8 235 5 8 -57 5 8 -225 5 8 -361 5 8 -161 5 8 -373 5 8 -129 5 8 23 5 8 -177 5 8 -65 5 8 -77 5 8 -353 5 8 267 5 8 -69 5 8 147 5 8 227 5 8 351 5 8 -305 5 8 -1 5 8 -165 5 8 55 5 8 -257 5 8 263 5 8 -121 5 8 -221 5 8 -249 5 8 159 5 8 67 5 ...
output:
0
result:
ok answer is '0'
Test #45:
score: 0
Accepted
time: 2ms
memory: 4280kb
input:
200 105 73 42 -12 -5 3 174 119 65 102 71 41 -150 -97 -43 -282 -185 -87 60 43 27 93 65 38 177 121 66 -42 -25 -7 -168 -109 -49 -270 -177 -83 -120 -77 -33 -279 -183 -86 -96 -61 -25 18 15 13 -132 -85 -37 -48 -29 -9 -57 -35 -12 -264 -173 -81 201 137 74 -51 -31 -10 111 77 44 171 117 64 264 179 95 -228 -14...
output:
1
result:
ok answer is '1'
Test #46:
score: 0
Accepted
time: 2ms
memory: 4340kb
input:
200 105 73 42 -12 -5 3 174 119 65 102 71 41 -150 -97 -43 -282 -185 -87 60 43 27 93 65 38 177 121 66 -42 -25 -7 -168 -109 -49 -270 -177 -83 -120 -77 -33 -279 -183 -86 -96 -61 -25 18 15 13 -132 -85 -37 -48 -29 -9 -57 -35 -12 -264 -173 -81 201 137 74 -51 -31 -10 111 77 44 171 117 64 264 179 95 -228 -14...
output:
0
result:
ok answer is '0'
Test #47:
score: 0
Accepted
time: 2ms
memory: 4336kb
input:
200 105 73 42 -12 -5 3 174 119 65 102 71 41 -150 -97 -43 -282 -185 -87 60 43 27 93 65 38 177 121 66 -42 -25 -7 -168 -109 -49 -270 -177 -83 -120 -77 -33 -279 -183 -86 -96 -61 -25 18 15 13 -132 -85 -37 -48 -29 -9 -57 -35 -12 -264 -173 -81 201 137 74 -51 -31 -10 111 77 44 171 117 64 264 179 95 -228 -14...
output:
0
result:
ok answer is '0'
Test #48:
score: 0
Accepted
time: 82ms
memory: 4128kb
input:
200 -473 -322 -77 -13 618 479 -49 670 -221 85 -450 477 11 -136 39 49 48 -537 -687 14 -155 -289 176 399 213 -268 -263 19 2 -19 -23 -484 -137 451 -194 281 -509 264 -195 205 -48 571 -407 -310 -311 435 -354 -267 303 188 211 309 418 327 19 -366 541 -97 276 619 291 -240 -531 -583 248 -387 339 272 481 -145...
output:
1
result:
ok answer is '1'
Test #49:
score: 0
Accepted
time: 80ms
memory: 4060kb
input:
200 -473 -322 -77 463 -444 545 -49 670 -221 85 -450 477 -653 206 -343 49 48 -537 -303 -368 525 -289 176 399 213 -268 -263 19 2 -19 -23 -484 -137 451 -194 281 -509 264 -195 205 -48 571 -407 -310 -311 225 292 -483 -157 -446 139 481 -272 527 19 -366 541 -97 276 619 291 -240 -531 -583 248 -387 339 272 4...
output:
0
result:
ok answer is '0'
Test #50:
score: 0
Accepted
time: 87ms
memory: 4272kb
input:
200 -473 -322 -77 -13 618 479 -49 670 -221 85 -450 477 11 -136 39 49 48 -537 -687 14 -155 -289 176 399 213 -268 -263 19 2 -19 -23 -484 -137 451 -194 281 -509 264 -195 205 -48 571 -407 -310 -311 435 -354 -267 303 188 211 309 418 327 19 -366 541 -97 276 619 291 -240 -531 -583 248 -387 339 272 481 -145...
output:
0
result:
ok answer is '0'
Test #51:
score: 0
Accepted
time: 84ms
memory: 4232kb
input:
200 387 5 8 35 5 8 -73 5 8 -353 5 8 -261 5 8 -61 5 8 -125 5 8 211 5 8 127 5 8 -237 5 8 99 5 8 -209 5 8 255 5 8 -137 5 8 347 5 8 -213 5 8 -97 5 8 187 5 8 -105 5 8 3 5 8 -113 5 8 -89 5 8 215 5 8 -249 5 8 243 5 8 -129 5 8 -93 5 8 319 5 8 -221 5 8 -201 5 8 -225 5 8 139 5 8 19 5 8 -1 5 8 -277 5 8 363 5 8...
output:
1
result:
ok answer is '1'
Test #52:
score: 0
Accepted
time: 81ms
memory: 4204kb
input:
200 387 5 8 35 5 8 -73 5 8 -353 5 8 -261 5 8 -61 5 8 -125 5 8 211 5 8 127 5 8 -237 5 8 99 5 8 -209 5 8 255 5 8 -137 5 8 347 5 8 -213 5 8 -97 5 8 187 5 8 -105 5 8 3 5 8 -113 5 8 -89 5 8 215 5 8 -249 5 8 243 5 8 -129 5 8 -93 5 8 319 5 8 -221 5 8 -201 5 8 -225 5 8 139 5 8 19 5 8 -1 5 8 -277 5 8 363 5 8...
output:
0
result:
ok answer is '0'
Test #53:
score: 0
Accepted
time: 80ms
memory: 4016kb
input:
200 387 5 8 35 5 8 -73 5 8 -353 5 8 -261 5 8 -61 5 8 -125 5 8 211 5 8 127 5 8 -237 5 8 99 5 8 -209 5 8 255 5 8 -137 5 8 347 5 8 -213 5 8 -97 5 8 187 5 8 -105 5 8 3 5 8 -113 5 8 -89 5 8 215 5 8 -249 5 8 243 5 8 -129 5 8 -93 5 8 319 5 8 -221 5 8 -201 5 8 -225 5 8 139 5 8 19 5 8 -1 5 8 -277 5 8 363 5 8...
output:
0
result:
ok answer is '0'
Test #54:
score: 0
Accepted
time: 80ms
memory: 4056kb
input:
200 291 197 104 27 21 16 -54 -33 -11 -264 -173 -81 -195 -127 -58 -45 -27 -8 -93 -59 -24 159 109 60 96 67 39 -177 -115 -52 75 53 32 -156 -101 -45 192 131 71 -102 -65 -27 261 177 94 -159 -103 -46 -72 -45 -17 141 97 54 -78 -49 -19 3 5 8 -84 -53 -21 -66 -41 -15 162 111 61 -186 -121 -55 183 125 68 -96 -6...
output:
1
result:
ok answer is '1'
Test #55:
score: 0
Accepted
time: 81ms
memory: 4128kb
input:
200 291 197 104 27 21 16 -54 -33 -11 -264 -173 -81 -195 -127 -58 -45 -27 -8 -93 -59 -24 159 109 60 96 67 39 -177 -115 -52 75 53 32 -156 -101 -45 192 131 71 -102 -65 -27 261 177 94 -159 -103 -46 -72 -45 -17 141 97 54 -78 -49 -19 3 5 8 -84 -53 -21 -66 -41 -15 162 111 61 -186 -121 -55 183 125 68 -96 -6...
output:
0
result:
ok answer is '0'
Test #56:
score: 0
Accepted
time: 81ms
memory: 4092kb
input:
200 291 197 104 27 21 16 -54 -33 -11 -264 -173 -81 -195 -127 -58 -45 -27 -8 -93 -59 -24 159 109 60 96 67 39 -177 -115 -52 75 53 32 -156 -101 -45 192 131 71 -102 -65 -27 261 177 94 -159 -103 -46 -72 -45 -17 141 97 54 -78 -49 -19 3 5 8 -84 -53 -21 -66 -41 -15 162 111 61 -186 -121 -55 183 125 68 -96 -6...
output:
0
result:
ok answer is '0'
Test #57:
score: 0
Accepted
time: 0ms
memory: 4288kb
input:
4 1 0 0 2 0 0 2 1 0 2 -1 0 1 2 1 3 2 4 0 1 1 0 0 0 0 2 0 0 0 2 5 6 5 7 5 8
output:
0
result:
ok answer is '0'
Test #58:
score: 0
Accepted
time: 2ms
memory: 4080kb
input:
200 -200 -520 192 -216 -610 -266 -428 46 -248 30 92 -36 -558 -534 332 138 -42 -412 240 286 46 -196 -140 -32 408 -120 -544 -236 -434 24 534 276 596 -432 -68 -406 80 -294 442 160 174 -176 330 188 180 472 -390 -352 574 422 224 292 -264 -360 -156 340 -384 498 -156 580 500 354 -494 444 -32 540 -102 298 1...
output:
1
result:
ok answer is '1'
Test #59:
score: 0
Accepted
time: 0ms
memory: 4164kb
input:
200 -380 -610 462 -396 -700 4 -608 -44 22 -150 2 234 -738 -624 602 -42 -132 -142 60 196 316 -376 -230 238 228 -210 -274 -416 -524 294 354 186 866 -612 -158 -136 -100 -384 712 -20 84 94 150 98 450 292 -480 -82 394 332 494 112 -354 -90 -336 250 -114 318 -246 850 320 264 -224 264 -122 810 -282 208 286 ...
output:
0
result:
ok answer is '0'
Test #60:
score: 0
Accepted
time: 1ms
memory: 4120kb
input:
200 -380 -610 462 -396 -700 4 -608 -44 22 -150 2 234 -738 -624 602 -42 -132 -142 60 196 316 -376 -230 238 228 -210 -274 -416 -524 294 354 186 866 -612 -158 -136 -100 -384 712 -20 84 94 150 98 450 292 -480 -82 394 332 494 112 -354 -90 -336 250 -114 318 -246 850 320 264 -224 264 -122 810 -282 208 286 ...
output:
0
result:
ok answer is '0'
Test #61:
score: 0
Accepted
time: 2ms
memory: 4284kb
input:
200 -917 -637 399 574 -697 354 -614 626 807 556 866 -117 418 -775 852 439 122 -45 -644 512 150 658 -706 -816 97 -844 768 433 -784 -285 -14 620 486 649 -553 -159 499 482 546 -668 -46 -570 754 398 891 607 68 30 781 815 39 -515 -184 -417 118 -586 801 427 119 -153 37 482 297 -476 -190 -504 178 791 468 -...
output:
1
result:
ok answer is '1'
Test #62:
score: 0
Accepted
time: 2ms
memory: 4340kb
input:
200 -917 -637 399 574 -697 354 -614 626 807 556 866 -117 418 -775 852 439 122 -45 -644 512 150 658 -706 -816 97 -844 768 433 -784 -285 -14 620 486 649 -553 -159 499 482 546 -668 -46 -570 754 398 891 607 68 30 781 815 39 -515 -184 -417 118 -586 801 427 119 -153 37 482 297 -476 -190 -504 178 791 468 -...
output:
0
result:
ok answer is '0'
Test #63:
score: 0
Accepted
time: 1ms
memory: 4264kb
input:
200 -917 -637 399 574 -697 354 -614 626 807 556 866 -117 418 -775 852 439 122 -45 -644 512 150 658 -706 -816 97 -844 768 433 -784 -285 -14 620 486 649 -553 -159 499 482 546 -668 -46 -570 754 398 891 607 68 30 781 815 39 -515 -184 -417 118 -586 801 427 119 -153 37 482 297 -476 -190 -504 178 791 468 -...
output:
0
result:
ok answer is '0'
Test #64:
score: 0
Accepted
time: 2ms
memory: 4024kb
input:
200 160 -268 -288 28 588 548 180 -600 296 6 340 -66 10 56 -322 618 -372 130 -566 -38 -510 40 -498 -2 -336 -412 188 -548 -286 -550 -20 -110 -98 6 318 180 -372 276 -114 392 -98 402 602 272 -30 268 -12 542 -210 -322 374 270 -558 244 -28 202 562 148 -458 494 -420 -42 188 -236 -278 -160 -110 -424 418 514...
output:
1
result:
ok answer is '1'
Test #65:
score: 0
Accepted
time: 0ms
memory: 4272kb
input:
200 160 -268 -288 28 588 548 180 -600 296 6 340 -66 10 56 -322 618 -372 130 -566 -38 -510 40 -498 -2 -336 -412 188 -548 -286 -550 -20 -110 -98 6 318 180 -372 276 -114 392 -98 402 602 272 -30 268 -12 542 -210 -322 374 270 -558 244 -28 202 562 148 -458 494 -420 -42 188 -236 -278 -160 -110 -424 418 514...
output:
0
result:
ok answer is '0'
Test #66:
score: 0
Accepted
time: 0ms
memory: 4192kb
input:
200 160 -268 -288 28 588 548 180 -600 296 6 340 -66 10 56 -322 618 -372 130 -566 -38 -510 40 -498 -2 -336 -412 188 -548 -286 -550 -20 -110 -98 6 318 180 -372 276 -114 392 -98 402 602 272 -30 268 -12 542 -210 -322 374 270 -558 244 -28 202 562 148 -458 494 -420 -42 188 -236 -278 -160 -110 -424 418 514...
output:
0
result:
ok answer is '0'
Test #67:
score: 0
Accepted
time: 0ms
memory: 4024kb
input:
200 61 112 145 55 -98 176 235 -88 126 5 -5 -12 -251 34 75 51 -254 196 158 304 286 151 -268 152 -38 302 10 -32 148 131 205 140 -92 -161 13 -215 -199 -181 -255 -300 -118 3 93 136 -88 173 222 17 -164 95 -128 -192 -107 -264 136 -190 -27 -164 -29 -95 -115 -59 -245 -82 -184 136 -228 297 59 -169 -103 -86 -...
output:
1
result:
ok answer is '1'
Test #68:
score: 0
Accepted
time: 1ms
memory: 4124kb
input:
200 61 112 145 55 -98 176 235 -88 126 5 -5 -12 -251 34 75 51 -254 196 158 304 286 151 -268 152 -38 302 10 -32 148 131 205 140 -92 -161 13 -215 -199 -181 -255 -300 -118 3 93 136 -88 173 222 17 -164 95 -128 -192 -107 -264 136 -190 -27 -164 -29 -95 -115 -59 -245 -82 -184 136 -228 297 59 -169 -103 -86 -...
output:
0
result:
ok answer is '0'
Test #69:
score: 0
Accepted
time: 1ms
memory: 4100kb
input:
200 61 112 145 55 -98 176 235 -88 126 5 -5 -12 -251 34 75 51 -254 196 158 304 286 151 -268 152 -38 302 10 -32 148 131 205 140 -92 -161 13 -215 -199 -181 -255 -300 -118 3 93 136 -88 173 222 17 -164 95 -128 -192 -107 -264 136 -190 -27 -164 -29 -95 -115 -59 -245 -82 -184 136 -228 297 59 -169 -103 -86 -...
output:
0
result:
ok answer is '0'
Test #70:
score: 0
Accepted
time: 0ms
memory: 4064kb
input:
4 1 0 0 2 0 0 2 2 0 2 -1 0 1 2 2 3 2 4 0 1 1 0 0 0 0 2 0 0 0 2 5 6 5 7 5 8
output:
0
result:
ok answer is '0'
Test #71:
score: 0
Accepted
time: 0ms
memory: 4228kb
input:
7 0 0 0 0 3 0 -3 3 0 0 6 0 0 9 0 0 9 3 0 9 -3 1 2 2 3 2 5 3 4 3 6 4 7 0 0 0 2 0 0 2 2 0 4 0 0 6 0 0 6 0 2 6 0 -2 8 9 9 10 9 12 10 11 10 13 11 14
output:
1
result:
ok answer is '1'
Test #72:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
7 0 0 0 0 3 0 -3 3 0 0 6 0 0 9 0 0 9 3 0 9 -3 1 2 2 3 2 5 3 4 3 6 4 7 0 0 0 2 0 0 2 2 0 4 0 0 6 0 0 6 0 2 6 0 -2 8 9 9 10 9 12 10 11 10 14 11 13
output:
0
result:
ok answer is '0'
Test #73:
score: 0
Accepted
time: 0ms
memory: 4220kb
input:
7 0 0 0 0 3 0 -3 3 0 0 6 0 0 9 0 0 9 3 0 9 -3 1 2 2 3 2 5 3 4 3 6 4 7 0 0 0 2 0 0 2 2 0 4 0 0 6 -4 0 6 0 2 6 0 -2 8 9 9 10 9 12 10 11 10 13 11 14
output:
0
result:
ok answer is '0'
Test #74:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
4 0 0 0 1 3 0 5 4 0 3 5 3 1 2 1 3 1 4 0 0 0 -1 3 0 -5 4 0 -3 5 3 5 6 5 7 5 8
output:
0
result:
ok answer is '0'
Test #75:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
3 0 0 0 0 0 1 0 0 2 1 2 1 3 10 4 6 0 0 0 5 2 3 4 5 5 6
output:
1
result:
ok answer is '1'
Test #76:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
4 0 0 0 1 3 3 -1 5 5 -10 2 2 1 2 1 3 1 4 1 1 6 0 0 0 -1 -1 10 -10 -10 4 5 6 6 7 6 8
output:
1
result:
ok answer is '1'
Test #77:
score: 0
Accepted
time: 0ms
memory: 4092kb
input:
7 0 0 0 1 0 0 -1 0 0 0 1 0 0 -1 0 0 0 1 0 0 -1 1 2 1 3 1 4 1 5 1 6 1 7 0 0 0 2 0 0 -2 0 0 0 2 0 0 -2 0 0 0 2 0 0 -2 8 9 8 10 8 11 8 12 8 13 8 14
output:
24
result:
ok answer is '24'
Test #78:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
4 0 0 0 89 89 0 -45 -44 109 -44 -45 -109 1 2 1 3 1 4 0 0 0 4 5 11 -9 -9 0 5 4 -11 5 6 5 7 5 8
output:
6
result:
ok answer is '6'
Test #79:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
5 0 0 0 9 9 0 -5 -4 11 -4 -5 -11 11 -11 1 1 2 1 3 1 4 1 5 0 0 0 4 5 11 -9 -9 0 5 4 -11 11 -11 1 6 7 6 8 6 9 6 10
output:
3
result:
ok answer is '3'
Test #80:
score: 0
Accepted
time: 0ms
memory: 4072kb
input:
4 0 0 0 9 9 0 -5 -4 11 -4 -5 -11 1 2 1 3 1 4 0 0 0 4 5 11 -9 -9 0 5 4 -11 5 6 5 7 5 8
output:
6
result:
ok answer is '6'
Test #81:
score: 0
Accepted
time: 0ms
memory: 4144kb
input:
7 0 0 0 9 9 0 4 5 11 -5 -4 11 -9 -9 0 -4 -5 -11 5 4 -11 1 2 1 3 1 4 1 5 1 6 1 7 0 0 0 89 89 0 44 45 109 -45 -44 109 -89 -89 0 -44 -45 -109 45 44 -109 8 9 8 10 8 11 8 12 8 13 8 14
output:
12
result:
ok answer is '12'
Test #82:
score: 0
Accepted
time: 0ms
memory: 4156kb
input:
7 0 0 0 9 9 0 4 5 11 -5 -4 11 -9 -9 0 -4 -5 -11 5 4 -11 1 2 1 3 1 4 1 5 1 6 1 7 0 0 0 9 9 0 4 5 11 -5 -4 11 -9 -9 0 -4 -5 -11 5 4 -11 8 9 8 10 8 11 8 12 8 13 8 14
output:
12
result:
ok answer is '12'
Test #83:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
4 0 0 0 1 0 0 0 1 0 0 0 1 1 2 1 3 1 4 0 0 0 2 0 0 0 2 0 0 0 2 5 6 5 7 5 8
output:
3
result:
ok answer is '3'