QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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;
}
Details
Tip: Click on the bar to expand more detailed information
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 ...