Submission #1070057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070057		BigBadBully	Sprinklers (CEOI24_sprinklers)	C++17	9 / 100	202 ms	12400 KiB

Main

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pii pair<int,int>
pii bad = {-1,-1};
const int jonkler = 1e15;
signed main() {
    int n,m;
    cin >> n >> m;
    vector<int> a(n),b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 0; i < m; i++)
        cin >> b[i];
    set<int> as,bs;
    for (int i = 0; i < n; i++)
    {
        as.insert(a[i]);
    }
    for (int i = 0; i < m; i++)
        if (as.find(b[i]) == as.end())
            bs.insert(b[i]);
    vector<int> neu;
    for (int i : bs)
        neu.push_back(i);
    b = neu;
    auto solve = [&](int k)
    {
        queue<pii> all;
        int i = 0,  j = 0;
        
        while(i < n && j < m)
        {
            if (a[i] < b[j])
                all.push({a[i++],1});
            else 
                all.push({b[j++],0});
            
        }
       while (i<n) all.push({a[i++],1});
        while (j<m) all.push({b[j++],0});
        int prev = jonkler;
        int range = -1;
       
        while (all.size())
        {
            auto cur = all.front();
            if (cur.ss)
            {
                if (prev == jonkler)
                range = cur.ff+k;
                else
                {
                    if (prev < cur.ff - k)
                    {
                        return 0;
                    }
                    else
                        prev = jonkler;
                }
            }
            else
            {
                if (cur.ff>range)
                prev = min(prev,cur.ff);
            }
            all.pop();
        }
        if (prev > range && prev != jonkler)
            return 0;
        return 1;
    };
    int l = 0, r = 1e10;
    while(r-l>1)
    {
        int mid = l+r>>1;
        if (solve(mid))
            r = mid;
        else
            l = mid;
    }
    string ans;
    auto fillstr = [&](int k)
    {
        queue<pii> all;
        int i = 0,  j = 0;
        while(i < n && j < m)
        {
            if (a[i] < b[j])
                all.push({a[i++],1});
            else
                all.push({b[j++],0});
        }
       while (i<n) all.push({a[i++],1});
        while (j<m) all.push({b[j++],0});
        int prev = jonkler;
        int range = -1;
       
        while (all.size())
        {
            auto cur = all.front();
            if (cur.ss)
            {
                if (prev == jonkler)
                {
                    range = cur.ff+k;
                    ans.push_back('R');
                }
                else
                {
                    
                    prev = jonkler;
                    ans.push_back('L');
                }
            }
            else
            {
                if (cur.ff>range)
                prev = min(prev,cur.ff);
            }
            all.pop();
        }
        
    };
    if (r == 1e10)
        cout << "-1\n";
    else
    {
    if (solve(l))
    {
        cout << l << '\n';
        fillstr(l);
        cout << ans << '\n';
      
    }
    else
    {
        cout << r << '\n';
        fillstr(r);
         cout << ans << '\n';
    }
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:80:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int mid = l+r>>1;
      |                   ~^~

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