oj.uz

Submission #1074900

# Submission time Handle Problem Language Result Execution time Memory
1074900 2024-08-25T16:17:21 Z anton Sprinklers (CEOI24_sprinklers) C++17
33 / 100
 558 ms 8984 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

vector<int> flowers;
vector<int> sprinklers;


int under(vector<int>& v, int x){
    int res =0;
    for(int step= (1<<20); step>=1; step/=2){
        if(res + step < v.size() && v[res+step]<=x){
            res+= step;
        }
    }

    return res;
}

int above(vector<int>& v, int x){
    int res =v.size()-1;
    for(int step= (1<<20); step>=1; step/=2){
        if(res - step >=0 && v[res-step]>=x){
            res-= step;
        }
    }
    return res;
}


pii get_coverage(pii interval){
    return {above(flowers, interval.first), under(flowers, interval.second)};
}

bool is_in(pii inter, int pos){
    return (pos>=inter.first && pos<=inter.second);
}

int N, M;

struct DP{
    int val= 0;
    int anc =0;
    string p;
    DP(){};
    DP(int _val, int _anc, string s){
        p = s;
        val = _val;
        anc= _anc;
    }
};

void chmax(DP& a, DP b){
    if(b.val>a.val){
        a= b;
    }
}

vector<DP> solve(int k){
    vector<DP> dp(N+1);

    for(int cur_sprinkler = 0; cur_sprinkler<N; cur_sprinkler++){
        int uncovered_flower = dp[cur_sprinkler].val;
        pii before_inter = get_coverage({sprinklers[cur_sprinkler]-k, sprinklers[cur_sprinkler]});
        if(is_in(before_inter, uncovered_flower)){
            chmax(dp[cur_sprinkler+1], DP(before_inter.second+1, cur_sprinkler, string("L")));
        }
        before_inter = get_coverage({sprinklers[cur_sprinkler], sprinklers[cur_sprinkler]+k});
        if(is_in(before_inter, uncovered_flower)){
            chmax(dp[cur_sprinkler+1], DP(before_inter.second+1, cur_sprinkler, string("R")));
        }

        if(cur_sprinkler<N-1){
            if(sprinklers[cur_sprinkler+1]-sprinklers[cur_sprinkler]<k){
                pii interval = {sprinklers[cur_sprinkler+1]-k, sprinklers[cur_sprinkler]+k};
                if(is_in(get_coverage(interval), uncovered_flower)){
                    chmax(dp[cur_sprinkler+2], DP(before_inter.second+1, cur_sprinkler, string("LR")));

                }
            }
        }

        chmax(dp[cur_sprinkler+1], DP(uncovered_flower, cur_sprinkler, string("R")));

    }

    return dp;
}

string res;
void backtrack(vector<DP>& dp, int pos){
    bool ok = true;
    while(ok){
        res.append(dp[pos].p.begin(), dp[pos].p.end());
        pos= dp[pos].anc;
        ok = pos>0;
    }
}
signed main(){
    cin>>N>>M;
    sprinklers.resize(N);

    for(int i = 0; i<N; i++){
        cin>>sprinklers[i];
    }

    int k;
    flowers.push_back(sprinklers[0]);
    for(int i = 0; i<M; i++){
        cin>>k;
        flowers.push_back(k);
    }

    flowers.push_back(sprinklers.back());

    sort(flowers.begin(), flowers.end());
    int K=1e9;

    for(int step = (1<<30); step>=1; step/=2){
        if(K-step>=0 && solve(K-step).back().val == M+2){
            K-=step;
        }
    }

    cout<<K<<endl;
    auto res_dp = solve(K);
    backtrack(res_dp, N);

    reverse(res.begin(), res.end());

    cout<<res<<endl;
}

Compilation message

Main.cpp: In function 'long long int under(std::vector<long long int>&, long long int)':
Main.cpp:15:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         if(res + step < v.size() && v[res+step]<=x){
      |            ~~~~~~~~~~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Incorrect 0 ms 436 KB User solution is incorrect
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 436 KB User solution is incorrect
2 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 32 ms 2384 KB Correct
3 Correct 43 ms 1116 KB Correct
4 Correct 492 ms 8908 KB Correct
5 Correct 549 ms 8816 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 524 ms 8984 KB Correct
9 Correct 539 ms 8816 KB Correct
10 Correct 558 ms 8816 KB Correct
11 Correct 303 ms 7164 KB Correct
12 Correct 206 ms 4564 KB Correct
13 Correct 394 ms 7760 KB Correct
14 Correct 385 ms 7976 KB Correct
15 Correct 432 ms 8048 KB Correct
16 Correct 452 ms 7880 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Incorrect 0 ms 436 KB User solution is incorrect
3 Halted 0 ms 0 KB -

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 62 ms 2764 KB Correct
3 Correct 409 ms 8792 KB Correct
4 Correct 432 ms 8820 KB Correct
5 Correct 433 ms 8920 KB Correct
6 Correct 409 ms 8908 KB Correct
7 Correct 436 ms 8916 KB Correct
8 Correct 398 ms 8820 KB Correct
9 Correct 416 ms 8816 KB Correct
10 Correct 451 ms 8796 KB Correct
11 Correct 422 ms 8820 KB Correct
12 Correct 1 ms 348 KB Correct
13 Correct 0 ms 348 KB Correct
14 Correct 162 ms 7164 KB Correct
15 Correct 251 ms 7156 KB Correct
16 Correct 333 ms 7396 KB Correct
17 Correct 399 ms 7536 KB Correct
18 Correct 387 ms 7536 KB Correct
19 Correct 394 ms 7792 KB Correct
20 Correct 393 ms 8560 KB Correct
21 Correct 416 ms 8496 KB Correct
22 Correct 415 ms 8300 KB Correct
23 Correct 405 ms 8308 KB Correct
24 Correct 414 ms 8052 KB Correct
25 Correct 430 ms 8100 KB Correct
26 Correct 235 ms 5860 KB Correct
27 Correct 144 ms 3532 KB Correct
28 Correct 439 ms 7796 KB Correct
29 Correct 397 ms 7712 KB Correct
30 Correct 417 ms 7796 KB Correct
31 Correct 328 ms 7072 KB Correct

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Incorrect 0 ms 436 KB User solution is incorrect
3 Halted 0 ms 0 KB -