QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#293928 | #5251. Constellations | LaStataleBlue# | AC ✓ | 8844ms | 253892kb | C++20 | 2.4kb | 2023-12-29 23:24:08 | 2023-12-29 23:24:09 |
Judging History
answer
#pragma ide diagnostic ignored "misc-no-recursion"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double db;
#define TESTCASE 0
static constexpr int MAX_N = 5000;
static constexpr ll INF = 1e15;
struct frac {
ll num, den;
frac(ll num, ll den) : num(num), den(den) {}
bool operator<(const frac &other) const {
return num * other.den < other.num * den;
}
};
static ll sum_sq[MAX_N];
static ll sum_x[MAX_N], sum_y[MAX_N];
static int sz[MAX_N];
static map<int, set<pair<frac, int>>> stars;
static frac dist(int a, int b) {
return {
sz[b] * sum_sq[a] + sz[a] * sum_sq[b] - 2 * (sum_x[a] * sum_x[b] + sum_y[a] * sum_y[b]),
sz[a] * sz[b],
};
}
static void create(int a) {
auto &da = stars[a];
for (auto &[b, db]: stars) {
if (a == b) continue;
auto f = dist(a, b);
da.emplace(f, b);
db.emplace(f, a);
}
}
static void destroy(int a) {
for (auto [f, i]: stars[a]) {
stars[i].erase({f, a});
}
stars.erase(a);
}
static void solve([[maybe_unused]] int tc) {
int N;
cin >> N;
for (int i = 0; i < N; i++) {
int x, y;
cin >> x >> y;
sum_x[i] = x;
sum_y[i] = y;
sum_sq[i] = x * x + y * y;
sz[i] = 1;
}
for (int a = 0; a < N; a++) {
create(a);
}
for (int t = N; stars.size() > 1; t++) {
auto old_it = stars.cbegin();
auto old_dist = old_it->second.begin()->first;
for (auto it = stars.cbegin(); it != stars.cend(); it++) {
auto f = it->second.begin()->first;
if (f < old_dist) {
old_it = it;
old_dist = f;
}
}
int old = old_it->first;
int young = old_it->second.begin()->second;
destroy(old);
destroy(young);
sum_x[t] = sum_x[old] + sum_x[young];
sum_y[t] = sum_y[old] + sum_y[young];
sum_sq[t] = sum_sq[old] + sum_sq[young];
sz[t] = sz[old] + sz[young];
create(t);
cout << sz[t] << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
if (const char *f = getenv("REDIRECT_STDOUT"); f) {
freopen(f, "w", stdout);
}
int T = 1;
#if TESTCASE
cin >> T;
#endif
for (int t = 1; t <= T; t++) {
solve(t);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3568kb
input:
2 0 0 1 0
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 4520ms
memory: 253872kb
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: 4517ms
memory: 253712kb
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: 4574ms
memory: 253700kb
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: 4589ms
memory: 253868kb
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: 4937ms
memory: 253820kb
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: 4660ms
memory: 253772kb
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: 8114ms
memory: 253696kb
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: 7546ms
memory: 253868kb
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: 8125ms
memory: 253828kb
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: 8632ms
memory: 253744kb
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: 8649ms
memory: 253892kb
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: 8803ms
memory: 253820kb
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: 8844ms
memory: 253784kb
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: 8501ms
memory: 253744kb
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: 0ms
memory: 3588kb
input:
4 0 0 0 -1 0 1 0 2
output:
2 2 4
result:
ok 3 lines