QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90325 | #5251. Constellations | chiranko# | AC ✓ | 9394ms | 160032kb | C++11 | 2.4kb | 2023-03-22 17:53:34 | 2023-03-22 17:53:36 |
Judging History
answer
#include <bits/stdc++.h>
#include <random>
#define MP make_pair
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using DB = long double;
const int maxn = 2005;
int merge_time[maxn];
DB sumx[maxn][2], sumy[maxn][2], siz[maxn];
struct star{
DB value;
int id1, id2;
bool operator < (const star b)const{
if(value != b.value)
return value < b.value;
if(min(merge_time[id1], merge_time[id2]) != min(merge_time[b.id1], merge_time[b.id2]))
return min(merge_time[id1], merge_time[id2]) < min(merge_time[b.id1], merge_time[b.id2]);
return max(merge_time[id1], merge_time[id2]) < max(merge_time[b.id1], merge_time[b.id2]);
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
set<star> st;
for(int i = 1; i <= n; ++i){
cin >> sumx[i][0] >> sumy[i][0];
sumx[i][1] = sumx[i][0] * sumx[i][0];
sumy[i][1] = sumy[i][0] * sumy[i][0];
siz[i] = 1;
merge_time[i] = i;
}
auto calc_dist = [&](int i, int j) -> DB{
auto _x = sumx[i][1] * siz[j] + sumx[j][1] * siz[i] - 2 * sumx[i][0] * sumx[j][0];
auto _y = sumy[i][1] * siz[j] + sumy[j][1] * siz[i] - 2 * sumy[i][0] * sumy[j][0];
return 1.0 * (_x + _y) / siz[i] / siz[j];
};
auto rem = [&](int i, int j) -> void{
if(!siz[i] || !siz[j] || i == j)
return;
int u = min(i, j), v = max(i, j);
st.erase({calc_dist(u, v), u, v});
};
auto add = [&](int i, int j) -> void{
if(!siz[i] || !siz[j] || i == j)
return;
int u = min(i, j), v = max(i, j);
st.insert({calc_dist(u, v), u, v});
};
auto merge = [&](int i, int j, int now) -> void{
for(int k = 1; k <= n; ++k){
rem(i, k); rem(j, k);
}
siz[i] += siz[j];
siz[j] = 0;
sumx[i][0] += sumx[j][0]; sumx[i][1] += sumx[j][1];
sumy[i][0] += sumy[j][0]; sumy[i][1] += sumy[j][1];
sumy[j][0] = sumy[j][1] = sumx[j][0] = sumx[j][1] = 0;
merge_time[i] = now;
merge_time[j] = n * n;
for(int k = 1; k <= n; ++k){
add(i, k);
}
};
for(int i = 1; i <= n; ++i){
for(int j = i + 1; j <= n; ++j){
DB t = calc_dist(i, j);
st.insert({t, i, j});
}
}
for(int round = 1; round <= n - 1; ++round){
auto tp = *(st.begin());
st.erase(st.begin());
int u = tp.id1, v = tp.id2;
merge(u, v, n + round);
// cerr << "merge " << u << " " << v << '\n';
cout << siz[u] << '\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
input:
2 0 0 1 0
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 4261ms
memory: 159892kb
input:
2000 1000 -1000 1000 -999 1000 -998 1000 -997 1000 -996 1000 -995 1000 -994 1000 -993 1000 -992 1000 -991 1000 -990 1000 -989 1000 -988 1000 -987 1000 -986 1000 -985 1000 -984 1000 -983 1000 -982 1000 -981 1000 -980 1000 -979 1000 -978 1000 -977 1000 -976 1000 -975 1000 -974 1000 -973 1000 -972 1000...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 1999 lines
Test #3:
score: 0
Accepted
time: 4122ms
memory: 159960kb
input:
2000 -1000 1000 -999 1000 -998 1000 -997 1000 -996 1000 -995 1000 -994 1000 -993 1000 -992 1000 -991 1000 -990 1000 -989 1000 -988 1000 -987 1000 -986 1000 -985 1000 -984 1000 -983 1000 -982 1000 -981 1000 -980 1000 -979 1000 -978 1000 -977 1000 -976 1000 -975 1000 -974 1000 -973 1000 -972 1000 -971...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 1999 lines
Test #4:
score: 0
Accepted
time: 4114ms
memory: 159964kb
input:
2000 -1000 -1000 -999 -1000 -998 -1000 -997 -1000 -996 -1000 -995 -1000 -994 -1000 -993 -1000 -992 -1000 -991 -1000 -990 -1000 -989 -1000 -988 -1000 -987 -1000 -986 -1000 -985 -1000 -984 -1000 -983 -1000 -982 -1000 -981 -1000 -980 -1000 -979 -1000 -978 -1000 -977 -1000 -976 -1000 -975 -1000 -974 -10...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 1999 lines
Test #5:
score: 0
Accepted
time: 4129ms
memory: 159960kb
input:
2000 -1000 -1000 -1000 -999 -1000 -998 -1000 -997 -1000 -996 -1000 -995 -1000 -994 -1000 -993 -1000 -992 -1000 -991 -1000 -990 -1000 -989 -1000 -988 -1000 -987 -1000 -986 -1000 -985 -1000 -984 -1000 -983 -1000 -982 -1000 -981 -1000 -980 -1000 -979 -1000 -978 -1000 -977 -1000 -976 -1000 -975 -1000 -9...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 1999 lines
Test #6:
score: 0
Accepted
time: 6041ms
memory: 159896kb
input:
2000 1000 -250 1000 -249 1000 -248 1000 -247 1000 -246 1000 -245 1000 -244 1000 -243 1000 -242 1000 -241 1000 -240 1000 -239 1000 -238 1000 -237 1000 -236 1000 -235 1000 -234 1000 -233 1000 -232 1000 -231 1000 -230 1000 -229 1000 -228 1000 -227 1000 -226 1000 -225 1000 -224 1000 -223 1000 -222 1000 ...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 1999 lines
Test #7:
score: 0
Accepted
time: 4339ms
memory: 159896kb
input:
2000 0 -1000 0 -999 0 -998 0 -997 0 -996 0 -995 0 -994 0 -993 0 -992 0 -991 0 -990 0 -989 0 -988 0 -987 0 -986 0 -985 0 -984 0 -983 0 -982 0 -981 0 -980 0 -979 0 -978 0 -977 0 -976 0 -975 0 -974 0 -973 0 -972 0 -971 0 -970 0 -969 0 -968 0 -967 0 -966 0 -965 0 -964 0 -963 0 -962 0 -961 0 -960 0 -959 ...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 1999 lines
Test #8:
score: 0
Accepted
time: 8905ms
memory: 159976kb
input:
2000 -400 571 -725 636 -880 529 -657 372 -383 382 -746 888 -604 785 -497 557 -677 977 -562 917 -530 623 -636 535 -816 579 -633 428 -573 561 -496 479 -409 448 -570 379 -421 795 -827 865 -730 809 -423 984 -676 772 -398 816 -451 373 -756 777 -351 829 -954 345 -543 871 -595 521 -501 734 -378 769 -987 60...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 ...
result:
ok 1999 lines
Test #9:
score: 0
Accepted
time: 8761ms
memory: 159844kb
input:
2000 -946 966 -655 760 -539 413 -857 715 -668 993 -543 399 -724 415 -584 464 -364 541 -518 756 -966 790 -648 616 -654 419 -842 544 -714 482 -636 984 -904 343 -559 925 -440 494 -636 780 -695 494 -585 465 -487 396 -683 886 -949 959 -668 518 -780 583 -854 612 -786 601 -527 758 -444 563 -994 840 -575 49...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 ...
result:
ok 1999 lines
Test #10:
score: 0
Accepted
time: 8959ms
memory: 159864kb
input:
2000 -707 382 -500 486 -927 357 -972 984 -738 591 -535 766 -610 603 -582 908 -923 676 -689 828 -940 783 -502 728 -971 384 -873 909 -824 412 -532 805 -715 448 -972 748 -423 975 -355 915 -943 453 -740 998 -776 457 -395 764 -805 337 -650 520 -656 612 -1000 841 -758 423 -414 762 -443 674 -666 469 -814 6...
output:
2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 1999 lines
Test #11:
score: 0
Accepted
time: 9072ms
memory: 159920kb
input:
2000 0 0 0 -1 1 -1 -1 1 -1 2 1 -2 3 0 1 -4 3 -3 -2 -4 -1 5 5 3 3 -6 4 6 -6 -5 4 -7 -2 9 1 -9 7 7 4 10 7 9 5 10 6 11 -5 12 -13 4 -5 13 14 2 10 11 -6 14 16 -1 11 -12 -14 -9 -14 11 15 11 -16 9 6 18 0 20 13 -15 9 -19 -10 -19 -21 8 -4 -22 -23 0 16 17 12 -21 -22 12 4 25 -14 -21 -7 -25 -3 -27 -27 1 23 16 1...
output:
2 2 2 2 2 2 2 2 2 2 2 2 4 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 5 2 2 2 2 2 2 2 2 2 2 2 2 2 7 5 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 9 3 2 2 2 2 2 2 3 3 3 6 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 8 2 2 2 2 2 2 2 2 2 3 3 4 4 2 2 2 2 11 3 3 2 2 2 2 2 2 4 2 2 2 2 2 2 2 2 2...
result:
ok 1999 lines
Test #12:
score: 0
Accepted
time: 8837ms
memory: 159916kb
input:
2000 0 0 -1 0 1 -1 0 -2 -1 -2 1 3 -3 1 3 2 -4 -1 -2 -4 4 4 -5 -3 -6 3 3 6 6 5 -7 4 -9 -2 8 5 3 -9 3 -10 11 0 8 -9 -6 -11 11 -7 6 12 -7 -12 0 -14 14 -5 -15 -1 -4 -15 -2 -16 -13 11 -15 -9 8 16 -18 -6 18 5 -16 12 -9 18 -1 -21 -15 -15 4 -22 -22 4 7 -22 19 -14 16 -18 15 19 -5 25 2 26 -1 26 -7 -26 23 -16 ...
output:
2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 4 3 3 2 2 2 2 2 2 7 2 2 2 2 2 2 2 2 2 2 2 2 2 9 2 2 2 2 2 2 2 2 2 6 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 2 2 2 2 2 3 3 2 2 2 2 2 2 2 2 2 5 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 3 4 2 2 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 1999 lines
Test #13:
score: 0
Accepted
time: 9137ms
memory: 160032kb
input:
2000 44 -748 385 448 -556 196 -569 -152 25 178 -865 609 644 -339 780 -558 429 676 469 712 876 987 -21 705 -742 679 375 970 -884 186 158 -340 -665 -673 153 484 -662 155 879 -724 -490 -785 -273 641 318 557 377 -706 260 695 -657 -926 -561 -315 861 -328 836 253 432 -505 -229 832 -774 -194 866 -951 171 6...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 3 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 1999 lines
Test #14:
score: 0
Accepted
time: 9394ms
memory: 159912kb
input:
2000 594 213 978 59 312 909 -226 -78 361 -398 -349 80 -9 -489 862 -525 -104 442 817 901 -243 921 -398 -185 279 -86 29 971 161 187 103 920 -825 -631 997 -179 -883 -78 442 322 463 -867 174 836 -92 308 179 -281 -960 578 513 -27 -436 -585 435 -621 -630 898 816 -515 693 205 -855 -124 27 -819 5 325 -510 -...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 1999 lines
Test #15:
score: 0
Accepted
time: 9265ms
memory: 159896kb
input:
2000 30 -912 687 32 -171 -142 320 -399 -304 640 -449 -761 -616 -493 -948 -63 -597 689 821 -935 -24 959 -568 78 -311 -446 929 733 -41 497 -345 909 131 -65 626 143 93 317 240 -796 165 193 -435 -211 -413 -830 845 -457 261 -508 -561 732 -194 934 -615 761 762 -370 614 -348 -663 720 -857 -457 695 -769 668...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 1999 lines
Test #16:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
4 0 0 0 -1 0 1 0 2
output:
2 2 4
result:
ok 3 lines