제출 #1323556

#제출 시각아이디문제언어결과실행 시간메모리
1323556TymondSprinklers (CEOI24_sprinklers)C++20
0 / 100
112 ms6224 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        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);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

const int MAXN = 1e5 + 7;
int n, m;
vi a;
set<pii> b;
vi B;
string ans = "";
pii dp[MAXN][(1 << 3)];
int pre[MAXN][(1 << 3)];

bool inside(int x, int msk, int K, int ind){
    for(int j = ind; j <= ind + 2; j++){
        if((1 << (j - ind)) & msk){
            if(B[x] >= a[j] && B[x] <= a[j] + K){
                return true;
            }
        }else{
            if(B[x] <= a[j] && B[x] >= a[j] - K){
                return true;
            }
        }
    }
    return false;
}

bool check(int K){
    //b - kwiatki
    for(int msk = 0; msk < (1 << 3); msk++){
        int wsk = 0;
        while(wsk < sz(B) && inside(wsk, msk, K, 0)){
            wsk++;
        }

        dp[2][msk] = mp(-1, -1);
        for(int j = 0; j < 3; j++){
            if((1 << j) & msk){
                dp[2][msk].se = max(dp[2][msk].se, a[j] + K);
            }else{
                dp[2][msk].se = max(dp[2][msk].se, a[j]);
            }
        }

        dp[2][msk].fi = wsk;
    }

    for(int i = 3; i < n; i++){
        for(int msk = 0; msk < (1 << 3); msk++){
            for(int prevAdd = 0; prevAdd < 2; prevAdd++){
                int prevMsk = msk / 2 + (1 << 2) * prevAdd;
                if(dp[i - 1][prevMsk].fi < sz(B) && B[dp[i - 1][prevMsk].fi] < a[i] - K){
                    dp[i][msk].fi = dp[i - 1][prevMsk].fi;
                    continue;
                }
                if(msk & 1){
                    //i-ty w prawo
                    dp[i][msk].se = max(dp[i - 1][prevMsk].se, a[i] + K);
                    if(dp[i - 1][prevMsk].fi < sz(B) && B[dp[i - 1][prevMsk].fi] >= a[i]){
                        auto it = b.upper_bound(mp(dp[i][msk].se, 0));
                        if(it == b.end()){
                            dp[i][msk].fi = sz(B);
                        }else{
                            dp[i][msk].fi = (*it).se;
                        }
                    }else{
                        dp[i][msk].fi = dp[i - 1][prevMsk].fi;
                    }
                }else{
                    //i-ty w lewo
                    dp[i][msk].se = max(dp[i - 1][prevMsk].se, a[i]);
                    if(dp[i - 1][prevMsk].fi < sz(B)){
                        auto it = b.upper_bound(mp(dp[i][msk].se, 0));
                        if(it == b.end()){
                            dp[i][msk].fi = sz(B);
                        }else{
                            dp[i][msk].fi = (*it).se;
                        }
                    }else{
                        dp[i][msk].fi = dp[i - 1][prevMsk].fi;
                    }
                }
            }
        }
    }

    for(int msk = 0; msk < (1 << 3); msk++){
        if(dp[n - 1][msk].fi == sz(B)){
            ans = "";
            int ind = n - 1;
            int curr = msk;
            while(ind > 2){
                if(curr & 1){
                    ans += "R";
                }else{
                    ans += "L";
                }
                curr = pre[ind][curr];
                ind--;
            }

            while(ind >= 0){
                if(curr & 1){
                    ans += "R";
                }else{
                    ans += "L";
                }
                ind--;
                curr /= 2;
            }
            reverse(all(ans));
            return true;
        }
    }
    return false;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    a.resize(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    while(sz(a) < 3){
        a.pb((int)2e9 + 7);
        n++;
    }

    B = {};
    for(int i = 0; i < m; i++){
        int x;
        cin >> x;
        B.pb(x);
        b.insert(mp(x, i));
    }

    int l = 0;
    int p = (int)1e9;
    int mid;
    while(l < p){
        mid = (l + p) / 2;
        if(check(mid)){
            p = mid;
        }else{
            l = mid + 1;
        }
    }

    if(!check(l)){
        cout << "-1\n";
        return 0;
    }

    cout << l << '\n';
    cout << ans << '\n';

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...