QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#590526#8066. Bombardmentnickbelov#RE 1100ms46720kbC++203.5kb2024-09-26 01:34:182024-09-26 01:34:19

Judging History

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

  • [2024-09-26 01:34:19]
  • 评测
  • 测评结果:RE
  • 用时:1100ms
  • 内存:46720kb
  • [2024-09-26 01:34:18]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;

struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;

void run()
{
    enum Day{
        open,close
    };
    ll n,R; cin >> n >> R;

    vll ans;
    vll v(n);for(ll &x : v) cin >> x;
    // ranges::sort(v);
    // auto u = ranges::unique(v);
    // v.erase(A(u));

    struct Event{
        ll time,type;
    };
    auto cmp = [](Event a,Event b){
        if(a.time == b.time) return a.type==close;
        return a.time<b.time;
    };
    set<ll> del;
    vector<Event> sweep;
    for(ll x : v){
        sweep.push_back({x-R,open});
        sweep.push_back({x+R+1,close});
    } ranges::sort(sweep,cmp);

    while(not v.empty()){
        ll mx = 0;
        for(ll cur = 0; auto [time,type] : sweep){
            if(type==open and del.contains(time+R)) continue;
            if(type==close and del.contains(time-R-1)) continue;
            if(type==open) cur++;
            else cur--;
            mx = max(cur,mx);
        }

        ll bomb_spot = -(ll)1e9;
        for(ll cur = 0; auto [time,type] : sweep){
            if(type==open and del.contains(time+R)) continue;
            if(type==close and del.contains(time-R-1)) continue;
            if(type==open) cur++;
            else cur--;
            if(cur==mx){
                bomb_spot=time;break;
            }
        }
        
        assert(bomb_spot not_eq -(ll)1e9);
        assert(mx);

        ans.push_back(bomb_spot);

        auto good = [&](ll spot){
            return abs(spot-bomb_spot)>R;
        };

        ranges::sort(v,[&](ll spot1,ll spot2){
            return !good(spot1)<!good(spot2);
        });

        while(not v.empty() and !good(v.back())) 
            del.insert(v.back()),v.pop_back();
    }

    cout << len(ans) << '\n';
    ranges::copy(ans,oit<ll>()),cout << '\n';
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    run();
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3532kb

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: 3476kb

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: 3748kb

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: 3524kb

input:

6 3
5 -2 5 0 1 2

output:

2
2 -5 

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 1100ms
memory: 46720kb

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: 3536kb

input:

1 1
0

output:

1
-1 

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 0ms
memory: 3404kb

input:

2 1
-1 1

output:

1
0 

result:

ok 2 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

2 1
1 -1

output:

1
0 

result:

ok 2 lines

Test #9:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

2 2
1 -1

output:

1
-1 

result:

ok 2 lines

Test #10:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

1 5000001
-100000000

output:

1
-105000001 

result:

ok 2 lines

Test #11:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

1 100000000
100000000

output:

1
0 

result:

ok 2 lines

Test #12:

score: 0
Accepted
time: 0ms
memory: 3408kb

input:

2 5000000
-100000000 100000000

output:

2
-105000000 95000000 

result:

ok 2 lines

Test #13:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

2 100000000
-100000000 100000000

output:

1
0 

result:

ok 2 lines

Test #14:

score: 0
Accepted
time: 0ms
memory: 3472kb

input:

2 99999999
-100000000 100000000

output:

2
-199999999 1 

result:

ok 2 lines

Test #15:

score: 0
Accepted
time: 0ms
memory: 3564kb

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: -100
Runtime Error

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:


result: