QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#824602 | #9776. Best Friend, Worst Enemy | ucup-team5052# | WA | 308ms | 14364kb | C++17 | 2.2kb | 2024-12-21 14:51:45 | 2024-12-21 14:51:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n, x[400005], y[400005], d1[400005], d2[400005], cnt[400005], idx[400005], inv[400005];
vector <int> psv;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int main() {
cin >> n;
for (int i = 1;i <= n;i++) {
cin >> x[i] >> y[i];
}
int p[2][2];
p[0][0] = p[0][1] = p[1][0] = p[1][1] = 1;
long long cx = rnd() % 20000 + 1, cy = rnd() % 20000 + 1;
cx -= 10000; cy -= 10000;
for (int i = 1;i <= n;i++) idx[i] = i;
sort(idx + 1, idx + n + 1, [&](const int &i, const int &j) {
return x[i] * cx + y[i] * cy < x[j] * cx + y[j] * cy;
});
for (int i = 1;i <= n;i++) inv[idx[i]] = i;
memset(d1, 0x3f, sizeof(d1));
for (int i = 1;i <= n;i++) {
vector <int> nxt;
for (int j : psv) {
if (max(abs(x[i] - x[j]), abs(y[i] - y[j])) < d1[j] || abs(x[i] - x[j]) + abs(y[i] - y[j]) > d2[j]) cnt[j] = 0;
d1[j] = min(d1[j], max(abs(x[i] - x[j]), abs(y[i] - y[j])));
d2[j] = max(d2[j], abs(x[i] - x[j]) + abs(y[i] - y[j]));
if (d1[j] == max(abs(x[i] - x[j]), abs(y[i] - y[j])) && d2[j] == abs(x[i] - x[j]) + abs(y[i] - y[j])) cnt[j]++;
if (2 * d1[j] >= d2[j]) nxt.push_back(j);
}
swap(psv, nxt);
for (int k1 = 0;k1 < 2;k1++) {
for (int k2 = 0;k2 < 2;k2++) {
if ((2 * k1 - 1) * x[i] + (2 * k2 - 1) * y[i] > (2 * k1 - 1) * x[p[k1][k2]] + (2 * k2 - 1) * y[p[k1][k2]]) {
p[k1][k2] = i;
}
d2[i] = max(d2[i], (2 * (!k1) - 1) * x[i] + (2 * (!k2) - 1) * y[i] + (2 * k1 - 1) * x[p[k1][k2]] + (2 * k2 - 1) * y[p[k1][k2]]);
}
}
int pos = inv[i];
cnt[i] = 0;
for (int jj = max(1, pos - 50);jj <= min(n, pos + 50);jj++) {
int j = idx[jj];
if (j >= i) continue;
if (max(abs(x[i] - x[j]), abs(y[i] - y[j])) < d1[i] || abs(x[i] - x[j]) + abs(y[i] - y[j]) > d2[i]) cnt[i] = 0;
d1[i] = min(d1[i], max(abs(x[i] - x[j]), abs(y[i] - y[j])));
d2[i] = max(d2[i], abs(x[i] - x[j]) + abs(y[i] - y[j]));
if (d1[i] == max(abs(x[i] - x[j]), abs(y[i] - y[j])) && d2[i] == abs(x[i] - x[j]) + abs(y[i] - y[j])) cnt[i]++;
}
// cout << d1[i] << " " << d2[i] << endl;
if (2 * d1[i] >= d2[i]) psv.push_back(i);
int ans = 0;
for (int j : psv) ans += cnt[j];
cout << ans << endl;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 13836kb
input:
2 1 5 1 10
output:
0 2
result:
ok 2 number(s): "0 2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11840kb
input:
4 2 5 5 3 5 7 8 5
output:
0 2 4 4
result:
ok 4 number(s): "0 2 4 4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 13904kb
input:
9 3 4 3 6 4 3 4 7 5 5 6 3 6 7 7 4 7 6
output:
0 2 1 0 4 5 6 7 8
result:
ok 9 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 9824kb
input:
13 3 5 4 4 4 5 4 6 5 3 5 4 5 5 5 6 5 7 6 4 6 5 6 6 7 5
output:
0 2 4 7 2 2 5 2 2 3 3 4 4
result:
ok 13 numbers
Test #5:
score: -100
Wrong Answer
time: 308ms
memory: 14364kb
input:
384010 200000 1000000 200000 1000001 199999 1000000 200001 1000000 200000 999999 200000 1000002 200002 1000000 200000 999998 199998 1000000 199997 1000000 200003 1000000 200000 999997 200000 1000003 199996 1000000 200004 1000000 200000 1000004 200000 999996 199995 1000000 200000 1000005 200000 99999...
output:
0 2 4 7 12 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
wrong answer 320008th numbers differ - expected: '6', found: '7'