QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#726595#8066. BombardmentTenshi#WA 148ms14940kbC++171.7kb2024-11-09 03:18:552024-11-09 03:18:57

Judging History

你现在查看的是最新测评结果

  • [2024-11-09 03:18:57]
  • 评测
  • 测评结果:WA
  • 用时:148ms
  • 内存:14940kb
  • [2024-11-09 03:18:55]
  • 提交

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;
}

详细

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'