QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #726596 | #8066. Bombardment | Tenshi# | TL | 0ms | 3812kb | C++17 | 1.8kb | 2024-11-09 03:24:04 | 2024-11-09 03:24:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using pii=pair<long long, int>;
#define rep(i, n) for (int i = 0; i < n; i++)
#define sz(x) (long long)(x).size()
int main(){
long long n, d; cin >> n >> d;
vector<int> points;
rep(i, n) {
int a; cin >> a;
points.push_back(a);
}
sort(points.begin(), points.end());
vector<pii> pts;
int laste = points[0];
int cnt = 1;
rep(i, n-1) {
if (points[i+1]==points[i]) cnt++;
else {
pts.push_back({laste, cnt});
cnt = 1;
laste = points[i+1];
}
}
pts.push_back({laste, cnt});
vector<bool> used (sz(pts), false);
vector<long long> out;
rep(iter, 40) {
int mxPts = 0;
long long mxidx = 1e9;
rep(l, sz(pts)) {
if (used[l]) continue;
int c = 0;
int r = l;
int last = l;
while (r < sz(pts) and pts[r].first - 2*d <= pts[l].first) {
if (!used[r]) c+=pts[r].second, last = r;
r++;
}
// cout << pts[l].first << ' ' << pts[last].first << endl;
if (c>mxPts) {
// cout << "YES" << endl;
mxPts = c;
mxidx = pts[last].first-2*d;
}
c-=pts[l].second;
}
if (mxidx==1e9) break;
out.push_back(mxidx+d);
rep(i, sz(pts)) {
if (pts[i].first >= mxidx and pts[i].first <= mxidx+2*d) used[i] = true;
// cout << used[i] << ' ';
}
// cout << endl;
}
cout << sz(out) << endl;
rep(i, sz(out)) {
cout << out[i] << ' ';
}
cout << endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
input:
7 1 1 2 3 3 4 4 5
output:
3 3 0 4
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
6 1 5 -2 5 0 1 2
output:
3 1 4 -3
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
6 2 5 -2 5 0 1 2
output:
2 0 3
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
6 3 5 -2 5 0 1 2
output:
2 2 -5
result:
ok 2 lines
Test #5:
score: -100
Time Limit Exceeded
input:
500000 25001 87425 164368 453013 281759 284570 187224 36997 420851 299754 449905 427728 327897 213484 414578 117919 430225 250744 108264 279365 398633 374591 449596 173533 132365 60100 123114 278 170508 116490 90071 381571 353436 302710 342319 410089 114375 345407 270822 264372 326998 345344 498062 ...