QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726595 | #8066. Bombardment | Tenshi# | WA | 148ms | 14940kb | C++17 | 1.7kb | 2024-11-09 03:18:55 | 2024-11-09 03:18:57 |
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, 20) {
int mxPts = 0;
int c = 0;
long long mxidx = 1e9;
int r = 0;
rep(l, sz(pts)) {
if (used[l]) continue;
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: 3476kb
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: 1ms
memory: 3792kb
input:
6 1 5 -2 5 0 1 2
output:
3 1 4 -3
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 3588kb
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: 3816kb
input:
6 3 5 -2 5 0 1 2
output:
2 2 -5
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 148ms
memory: 14940kb
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 ...
output:
10 25001 75004 125007 175010 225013 275016 325019 375022 425025 474998
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
1 1 0
output:
1 -1
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
2 1 -1 1
output:
1 0
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
2 1 1 -1
output:
1 0
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
2 2 1 -1
output:
1 -1
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
1 5000001 -100000000
output:
1 -105000001
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
1 100000000 100000000
output:
1 0
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
2 5000000 -100000000 100000000
output:
2 -105000000 95000000
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
2 100000000 -100000000 100000000
output:
1 0
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
2 99999999 -100000000 100000000
output:
2 -199999999 1
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
40 5000000 -90000000 -80000000 -30000000 90000000 50000000 20000000 -65000000 -60000000 80000000 55000000 30000000 65000000 85000000 25000000 45000000 -10000000 -15000000 -50000000 -40000000 -20000000 35000000 70000000 -35000000 -25000000 60000000 10000000 -55000000 -45000000 95000000 -70000000 0 -7...
output:
14 -95000000 -80000000 -65000000 -50000000 -35000000 -20000000 -5000000 10000000 25000000 40000000 55000000 70000000 85000000 90000000
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 133ms
memory: 5384kb
input:
500000 5000000 -15000000 -45000000 -25000000 -70000000 -15000000 -70000000 -70000000 85000000 95000000 -80000000 60000000 -55000000 -40000000 -70000000 -75000000 -30000000 25000000 -95000000 25000000 70000000 90000000 -70000000 60000000 -60000000 0 85000000 40000000 -35000000 70000000 -95000000 -850...
output:
16 -75000000 -30000000 65000000 -60000000 30000000 -90000000 45000000 80000000 -45000000 -15000000 90000000 5000000 15000000 -105000000 -10000000 50000000
result:
ok 2 lines
Test #17:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
10 572223 -2532666 -3003959 -8538825 9071942 -10475217 -3901005 -5116326 -3125580 -1195446 4299148
output:
8 -3576182 -11047440 -9111048 -5688549 -3104889 -1767669 3726925 8499719
result:
ok 2 lines
Test #18:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
100 2665309 10065248 25386613 50839193 -45145139 -15262316 -27823275 -45231498 1147086 -49534765 45305821 -47588528 -23883782 -43535631 -17224276 -987275 -22340945 -30880670 -48743202 7092883 -9574654 -12924292 9623463 21591733 -350435 -7213867 37104166 -36255841 10205742 -22739243 -24189117 -420853...
output:
20 -47187408 -15589601 494693 -25228700 7540433 38860848 -9879176 15202074 22721304 -38838401 -31449290 42640512 48861750 29261308 -23392117 -5460481 -55952996 -46200940 -15461111 1069092
result:
ok 2 lines
Test #19:
score: -100
Wrong Answer
time: 1ms
memory: 3860kb
input:
1000 1188209 -15798452 -20691057 -3153590 -20159606 14848680 -16938349 10640744 -4068675 17373400 2680130 11336281 20227094 17552257 13134395 12162537 16815587 -20944801 6731403 -2871158 -135237 22666190 7433801 17843386 12442717 16281655 -20208717 -23405037 5082386 -5225015 -2304002 -17486204 10937...
output:
20 -2898885 376225 -14657397 -20855468 -10150263 7323694 -7452829 21873990 15472438 12905550 -17673395 18069502 4115838 -5343919 10236003 -23292424 -12623984 1630616 19256376 -20167974
result:
wrong answer 1st lines differ - expected: '28', found: '20'