Submission #1199052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199052		BigBadBully	Sprinklers (CEOI24_sprinklers)	C++17	Compilation error	0 ms	0 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pid pair<int,double>
#define pii pair<int,int>
#define ff first
#define ss second
const int inf = 1e18;
const int maxn = 1e3;
using namespace std;


void solve()
{
    int n,m;
    cin >> n >> m;
    vector<int> va(n),vb(m);
    for (int i = 0; i < n; i++)
        cin >> va[i];
    for (int i = 0; i < m; i++)
        cin >> vb[i];
    set<int> svn;
    for (int x: va)
        svn.insert(x);
    vector<int> nvb;
    for (int i = 0; i < m; i++)
        if (!svn.count(vb[i]))
            nvb.push_back(vb[i]);
    //1 = R
    //0 = L
    m = nvb.size();
    vb = nvb;
    string bad = "l";
    auto calc = [&](int k)
    {
        vector<vector<pii>> seg(n);
        for (int i = 0; i < m; i++)
        {
            vector<int> mask;
            auto it2 = upper_bound(va.begin(),va.end(),vb[i]+k)-va.begin();
            auto it0 = lower_bound(va.begin(),va.end(),vb[i]-k)-va.begin();
            auto it1 = lower_bound(va.begin(),va.end(),vb[i])-va.begin();
            if (it0 >= n ||it2 == 0)
                return 0;
            for (int j = it0; j < it1; j++)
                mask.push_back(0);
            for (int j = it1; j < it2; j++)
                mask.push_back(1);
            if (count(mask.begin(),mask.end(),0) >= 3)
                seg[it2-1].push_back({3,0});          
            else if (count(mask.begin(),mask.end(),1) >= 3)
                seg[it2-1].push_back({3,(1<<3)-1});
            else
            {
            int sum = 0;
            int f = mask.size();
            for (int j = 0; j < f; j++)
                sum+=(1<<f-1-j)*mask[j];
            seg[it2-1].push_back({mask.size(),sum});
            }
        }
        
        array<int,8> prev,nxt;
        for (int i = 0; i < 8; i++)
            prev[i] = 0;
        vector<array<int,8>> dp(n);
        for (int i = 0; i < n; i++)
        {
            array<int,16> cands;
            for (int j = 0; j < 8; j++)
                cands[2*j] = (prev[j] != -1 ? j : -1),
                cands[2*j+1] = (prev[j] != -1 ? j : -1);
            for (auto x : seg[i])
                for (int cnt = 0; cnt < 16; cnt+=(1<<x.ff))
                    cands[x.ss+cnt] = -1;
            for (int j = 0; j < 8; j++)
                    prev[j]=(cands[j] != -1 ? cands[j] : cands[j+(1<<3)]);
            
            dp[i] = prev;
        }
        /*
        for (int j = 0; j < 8; j++)
            if (prev[j] != -1)
            {
                string ans;
                auto cur = j;
                for (int i = n-1; i >= 0; i--)
                    ans.push_back(cur%2 ? 'R' : 'L'),cur = dp[i][cur];
                reverse(ans.begin(),ans.end());
                return ans;
            }
        */
       for (int j = 0; j < 8; j++)
        if (prev[j]!=1)
            return 1;
        return 0;
    };
    auto calc_s = [&](int k)
    {
        vector<vector<pii>> seg(n);
        for (int i = 0; i < m; i++)
        {
            vector<int> mask;
            auto it2 = upper_bound(va.begin(),va.end(),vb[i]+k)-va.begin();
            auto it0 = lower_bound(va.begin(),va.end(),vb[i]-k)-va.begin();
            auto it1 = lower_bound(va.begin(),va.end(),vb[i])-va.begin();
            for (int j = it0; j < it1; j++)
                mask.push_back(0);
            for (int j = it1; j < it2; j++)
                mask.push_back(1);
            if (count(mask.begin(),mask.end(),0) >= 3)
                seg[it2-1].push_back({3,0});          
            else if (count(mask.begin(),mask.end(),1) >= 3)
                seg[it2-1].push_back({3,(1<<3)-1});
            else
            {
            int sum = 0;
            int f = mask.size();
            for (int j = 0; j < f; j++)
                sum+=(1<<f-1-j)*mask[j];
            seg[it2-1].push_back({mask.size(),sum});
            }
        }
        
        array<int,8> prev,nxt;
        for (int i = 0; i < 8; i++)
            prev[i] = 0;
        vector<array<int,8>> dp(n);
        for (int i = 0; i < n; i++)
        {
            array<int,16> cands;
            for (int j = 0; j < 8; j++)
                cands[2*j] = (prev[j] != -1 ? j : -1),
                cands[2*j+1] = (prev[j] != -1 ? j : -1);
            for (auto x : seg[i])
                for (int cnt = 0; cnt < 16; cnt+=(1<<x.ff))
                    cands[x.ss+cnt] = -1;
            for (int j = 0; j < 8; j++)
                    prev[j]=(cands[j] != -1 ? cands[j] : cands[j+(1<<3)]);
            
            dp[i] = prev;
        }
        
        for (int j = 0; j < 8; j++)
            if (prev[j] != -1)
            {
                string ans;
                auto cur = j;
                for (int i = n-1; i >= 0; i--)
                    ans.push_back(cur%2 ? 'R' : 'L'),cur = dp[i][cur];
                reverse(ans.begin(),ans.end());
                return ans;
            }
        return 0;
    };

    if (m==0)
    {
        cout << 0 <<'\n';
        cout << string(n,'L') << '\n';
        return;
    }
    int l = 0, r = 1e9;
    
    while(r-l)
    {
        int mid =l+r>>1;
        if (calc(mid))
            r = mid;
        else
            l = mid+1;
    }
    if (l==1e9)
        cout << -1 << endl;
    else
        cout << l << '\n' << calc_s(l) << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    int t = 1;
    //cin >> t;
    while(t--)
    solve();
}

Compilation message (stderr)

Main.cpp:9:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    9 | const int inf = 1e18;
      |                 ^~~~
Main.cpp: In lambda function:
Main.cpp:155:16: error: inconsistent types 'std::__cxx11::basic_string<char>' and 'int' deduced for lambda return type
  155 |         return 0;
      |                ^