Submission #1074900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074900		anton	Sprinklers (CEOI24_sprinklers)	C++17	33 / 100	558 ms	8984 KiB

Main

#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 (stderr)

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
• Subtask 1: 0 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 17
• Subtask 4: 27 / 27
• Subtask 5: 0 / 47