QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#89389 | #5251. Constellations | Milk_Feng | WA | 3671ms | 269792kb | C++ | 2.1kb | 2023-03-19 22:04:58 | 2023-03-19 22:05:00 |
Judging History
answer
#include <bits/stdc++.h>
#include <set>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
//typedef __int128 LLL;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') c == '-' ? f = -1: 0, c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ '0'), c = getchar();
return x * f;
}
LL X[5050], Y[5050], sz[5050], dis_[5050][5050];
struct Pair {
int i, j;
Pair(int _i, int _j): i(_i), j(_j) {}
bool operator < (const Pair &o) const {
int thisnew = max(i, j), thisold = min(i, j);
int othernew = max(o.i, o.j), otherold = min(o.i, o.j);
LL tmp1 = dis_[i][j] * sz[o.i] * sz[o.j];
LL tmp2 = dis_[o.i][o.j] * sz[i] * sz[j];
if(tmp1 == tmp2) {
if(thisold == otherold) return thisnew < othernew;
else return thisold < otherold;
}
else return tmp1 < tmp2;
}
};
set<Pair> s[4050];
set<int> exist;
signed main() {
int n = read();
for(int i = 1; i <= n; ++i) X[i] = read(), Y[i] = read();
for(int i = 1; i <= n; ++i) {
for(int j = i + 1; j <= n; ++j) {
dis_[i][j] = dis_[j][i] = (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]);
s[i].insert(Pair(i, j));
}
exist.insert(i);
sz[i] = 1;
}
while(exist.size() > 1) {
Pair mn = *s[*exist.begin()].begin();
for(int i: exist) {
if(s[i].empty()) continue;
Pair pair = *(s[i].begin());
if(pair < mn) mn = pair;
}
int id1 = mn.i, id2 = mn.j;
sz[++n] = sz[id1] + sz[id2];
for(int i: exist) dis_[i][n] = dis_[n][i] = dis_[i][id1] + dis_[i][id2];
for(int i: exist) if(i < id1) s[i].erase(Pair(i, id1));
for(int i: exist) if(i < id2) s[i].erase(Pair(i, id2));
for(int i: exist) if(i != id1 && i != id2) s[i].insert(Pair(i, n));
exist.erase(id1), exist.erase(id2);
exist.insert(n);
printf("%lld\n", sz[n]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3748kb
input:
2 0 0 1 0
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 2051ms
memory: 269532kb
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: 2038ms
memory: 269536kb
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: 2090ms
memory: 269532kb
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: 2001ms
memory: 269764kb
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: 2108ms
memory: 269792kb
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: 2140ms
memory: 269556kb
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: -100
Wrong Answer
time: 3671ms
memory: 204448kb
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 3 2 3 2 3 2 3 4 3 4 5 4 5 6 5 7 4 2 3 4 5 6 7 6 7 8 9 8 8 2 3 4 5 6 10 7 6 9 5 8 9 11 2 3 4 5 4 5 7 2 3 4 5 6 9 6 8 10 6 7 12 10 7 6 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 7 8 9 10 11 12 13 8 9 10 11 11 12 8 9 10 12 7 8 9 10 7 14 14 13 14 13 11 11 9 2 3 4 5 6 7 8 14 11 15 12 10 15 2 3 4 5 6 7 10 ...
result:
wrong answer 3rd lines differ - expected: '2', found: '3'