Submission #1037274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037274		12345678	Sprinklers (CEOI24_sprinklers)	C++17	100 / 100	130 ms	17416 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, mx=1e9+5, kx=10, bx=3;

int n, m, s[nx], f[nx], dr[nx], rv[nx][kx], l=0, r=1e9+5;
pair<int, int> dp[nx][kx];

bool solve(int x)
{
    for (int i=1; i<=n; i++) dr[i]=0;
    vector<int> vs(n+1), p, w;
    vector<pair<int, int>> range;
    p.push_back(0);
    for (int i=4; i<=n; i++)
    {
        if (!range.empty()&&range.back().second>=s[i]-1) vs[i]=1, range.back().second=s[i]+x;
        else if (s[i]-s[i-3]<=x) dr[i-3]=dr[i-1]=1, vs[i-3]=vs[i-2]=vs[i-1]=vs[i]=1, range.push_back({s[i-3]-x, s[i]+x});
    }
    for (int i=1; i<=n; i++) if (!vs[i]) p.push_back(i);
    int idx=0;
    for (int i=1; i<=m; i++)
    {
        while (idx<range.size()&&f[i]>range[idx].second) idx++;
        if (range.empty()||f[i]<range[idx].first||f[i]>range[idx].second) w.push_back(i);
    }
    w.push_back(m+1);
    vector<int> nxt(p.size()), nxtl(p.size());
    idx=0;
    for (int i=0; i<p.size(); i++)
    {
        while (f[w[idx]]<=s[p[i]]) idx++;
        nxt[i]=idx;
    }
    idx=0;
    for (int i=0; i<p.size(); i++)
    {
        while (f[w[idx]]<=s[p[i]]+x) idx++;
        nxtl[i]=idx;
    }
    if (p.size()==1) return (w.size()==1);
    for (int i=0; i<(1<<bx); i++) dp[0][i]={0, 0};
    for (int i=1; i<p.size(); i++)
    {
        for (int msk=0; msk<(1<<bx); msk++)
        {
            int a=msk/2, b=msk/2+(1<<(bx-1));
            if (dp[i-1][a].first<dp[i-1][b].first) swap(a, b);
            int loc=f[w[dp[i-1][a].first]];
            rv[i][msk]=a;
            if (msk&1)
            {
                if (loc>=s[p[i]]-x&&loc<=s[p[i]]) dp[i][msk]={max(dp[i-1][a].second, nxt[i]), max(dp[i-1][a].second, nxt[i])};
                else dp[i][msk]=dp[i-1][a];
            }
            else
            {
                if (loc>=s[p[i]]) dp[i][msk]={nxtl[i], nxtl[i]};
                else dp[i][msk]={dp[i-1][a].first, nxtl[i]};
            }
        }
    }
    for (int i=0; i<(1<<bx); i++) 
    {
        if (dp[p.size()-1][i].first==w.size()-1) 
        {
            int cur=i;
            for (int j=p.size()-1; j>0; j--) dr[p[j]]=cur%2, cur=rv[j][cur];
            return 1;
        }
    }
    return 0;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>s[i];
    for (int i=1; i<=m; i++) cin>>f[i];
    s[0]=-2e9;
    f[m+1]=INT_MAX;
    while (l<r)
    {
        int md=(l+r)/2;
        if (solve(md)) r=md;
        else l=md+1;
    }
    if (l==mx) return cout<<-1, 0;
    solve(l);
    cout<<l<<'\n';
    for (int i=1; i<=n; i++) cout<<(dr[i]?'L':'R');
}

Compilation message (stderr)

Main.cpp: In function 'bool solve(int)':
Main.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         while (idx<range.size()&&f[i]>range[idx].second) idx++;
      |                ~~~^~~~~~~~~~~~~
Main.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i=0; i<p.size(); i++)
      |                   ~^~~~~~~~~
Main.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i=0; i<p.size(); i++)
      |                   ~^~~~~~~~~
Main.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i=1; i<p.size(); i++)
      |                   ~^~~~~~~~~
Main.cpp:66:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if (dp[p.size()-1][i].first==w.size()-1)
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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