제출 #1212944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1212944		spetr	Sprinklers (CEOI24_sprinklers)	C++20	3 / 100	7 ms	1484 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mod = 1e9 + 9; 
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>

ll pow(ll x, ll n, ll mod){
    if (n == 0){
        return 1;
    }
ll half = pow(x, n / 2, mod);
ll half_square = (half * half) % mod;

if (n % 2 == 0) {
    return half_square;
} else {
    return (half_square * x) % mod;
}
}   


ll inversion_x(ll x, ll m){
    ll vysledek = pow(x,m-2);
    return vysledek;
}
ll n, m;
vl f, s;
vector<char> ans;

ll count(ll l, ll r, ll index){
    while(index < m && f[index] >= l && f[index] <= r){
        index++;
    }
    return index;
}


bool dyn(ll x){
    vl dp {0};
    vector<char> p;
    for (ll i = 0; i < n; i++){
        ll ndp = dp[dp.size()-1];
        char znak = 'L';

        ll novy = count(s[dp[dp.size()-1]] - x, s[dp[dp.size()-1]], dp[dp.size()-1]);
        ndp = max(novy, ndp);

        novy = count(s[dp[dp.size()-1]], s[dp[dp.size()-1]] + x, dp[dp.size()-1]);
        if (novy > ndp){
            znak = 'R';
            ndp = novy;
        }

        if (dp.size() > 1){
            novy = count(s[dp[dp.size()-1]]-x, s[dp[dp.size()-2]] + x, dp[dp.size()-2]);
            if (novy > ndp){
                znak = 'B';
                ndp = novy;
            }
        }

        dp.push_back(ndp);
        p.push_back(znak);
    }

    for (ll i = n-1; i >= 0; i--){
        if (p[i] == 'B'){
            ans[i] = 'L';
            ans[i-1] = 'R';
            i--;
        }
        else{
            ans[i] = p[i];
        }
    }

    return dp[n] == m; 


}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (ll i = 0; i < n; i++){
        ans.push_back('L');
    }
    

    for (ll i = 0; i < n; i++){
        ll num;
        cin >> num;
        s.push_back(num);

    }

    for (ll i = 0; i < m; i++){
        ll num;
        cin >> num;
        f.push_back(num);
    }

    ll l, r;
    l = -1;
    r = 1e10;
    ll mid = (l+r)/2;

    while (r-l > 1){
        bool test = dyn(mid);

        if (test == false){
            l = mid;
        }
        else{
            r = mid;
        }
        mid = (l+r)/2;
    }

    if (r == 1e10){
        cout << -1;
    }

    else{
        dyn(r);
        cout << r << "\n";
        for (ll i = 0; i < ans.size(); i++){
            cout << ans[i];
        }
    }


}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47