Submission #1140691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140691		hynmj	Sprinklers (CEOI24_sprinklers)	C++20	9 / 100	51 ms	2120 KiB

Main

//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define ll long long
#define ln cout<<endl
#define int long long
#define Code ios_base::sync_with_stdio(0);
#define by cin.tie(NULL);
#define Hayan cout.tie(NULL);
#define append push_back
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define vi vector<int>
#define ret(x) {cout<<x;return;}
#define ui map<int,int>
#define pi pair<int,int>
#define ff first
#define ss second
using namespace std;
template <typename T> using v = vector<T>;
const int INF = 1e18, MOD = 1e9+7, N = 2e5+7;
int a[N];
int b[N];
int n, k, e, m, ans = 0;
string s;
bool approved(int k)
{
    s.assign(n,'-');
    int j=0;
    for (int i=0;i<n;i++)
    {
        while (j<m and (s[i]=='L') and a[i]-k <=  b[j] and b[j] <= a[i])
        {
            j++;
        } 
        while (j<m and (s[i]=='R') and a[i] <=  b[j] and b[j] <= a[i] + k)
        {
            j++;
        } 
        if (s[i]=='-')
        {
            if (j<m and  a[i]-k <=  b[j] and b[j] < a[i] )
            {
                s[i]='L';
                j++;
            }
            else s[i]='R';
        }
        while (j<m and (s[i]=='L') and a[i]-k <=  b[j] and b[j] <= a[i])
        {
            j++;
        } 
        while (j<m and (s[i]=='R') and a[i] <=  b[j] and b[j] <= a[i] + k)
        {
            j++;
        } 
    }
    // cout <<j<<" "<<s<<endl;
    return j==m;
}
void solve()
{
    cin >> n >> m;
    rep(n)
    {
    	cin >> a[i];
    }
    rep(m)
    {
        cin>>b[i];
    }
    int l=-1,r=1e18;
    while (r-l>1)
    {
        int mid=(r+l)/2;
        if (approved(mid))
        {
            r=mid;
        }
        else l=mid;
    }
    if (approved(r))
    {
        cout <<r<<'\n'<<s<<endl;
    }
    else ret(-1)






    //  cout << approved(7);

    // cout << a.size();
    // for (auto i: a){cout << i << " ";}
}
signed main(){
    Code by Hayan
    int ans=1;
    //cout<<setprecision(1000);
    // cin>>ans;

    rep(ans){
        // cout << "Case #" << i+1 << ": ";
        solve();ln;}}

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