Submission #1320093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320093		HoriaHaivas	Sprinklers (CEOI24_sprinklers)	C++20	3 / 100	2095 ms	5856 KiB

Main

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

int s[100005];
bool done[100005];
int f[100005];
int furthest[100005];
int closest[100005];
int group[100005];
int groupend[100005];
int groupstart[100005];
int groupsz[100005];
vector<int> ls,rs;
string bigmeeks;
int n,m;

bool is_between(int l, int r)
{
    int re,pas;
    re=0;
    pas=(1<<16);
    while (pas)
    {
        if (re+pas<=n && f[re+pas]<=l)
            re+=pas;
        pas=pas/2;
    }
    re++;
    if (re<=n && l<f[re] && f[re]<r)
        return 1;
    else
        return 0;
}

bool ok(int k)
{
    int i,r,pas,bound,last,j,furthest1,closest1,l;
    bool oke;
    for (i=1; i<=m; i++)
    {
        r=0;
        pas=(1<<16);
        while(pas)
        {
            if (r+pas<=n && s[r+pas]<f[i])
                r+=pas;
            pas=pas/2;
        }
        r++;
        if (r<=n && f[i]+k>=s[r])
        {
            closest[i]=r;
            bound=groupend[group[r]];
            r=0;
            pas=(1<<16);
            while(pas)
            {
                if (r+pas<=bound && s[r+pas]<=f[i]+k)
                    r+=pas;
                pas=pas/2;
            }
            furthest[i]=r;
        }
        else
        {
            furthest[i]=n+1;
            closest[i]=n+1;
        }
    }
    string config;
    config="$";
    for (i=1; i<=n; i++)
        config+='R';
    for (i=1; i<=m; i++)
    {
        done[i]=0;
        r=0;
        pas=(1<<16);
        while (pas)
        {
            if (r+pas<=n && s[r+pas]<=f[i])
                r+=pas;
            pas=pas/2;
        }
        if (s[r]==f[i])
            done[i]=1;
    }
    for (i=1; i<=n; i++)
    {
        if (groupstart[group[i]]==i)
        {
            r=0;
            pas=(1<<16);
            while (pas)
            {
                if (r+pas<=m && f[r+pas]<=s[i])
                    r+=pas;
                pas=pas/2;
            }
            l=r+1;
            while (l<=n && f[l]<=s[i]+k)
            {
                done[l]=1;
                l++;
            }
        }
    }
    j=1;
    last=0;
    for (i=1; i<=m; i++)
    {
        if (!done[i])
        {
            furthest1=furthest[i];
            closest1=closest[i];
            if (furthest1==n+1 || f[i]==s[furthest1])
                continue;
            if ((furthest1-closest1+1)==1)
            {
                for (l=closest1; l<=furthest1; l++)
                    config[l]='L';
                while (j<=m && f[j]<=s[furthest1])
                {
                    done[j]=1;
                    j++;
                }
                last=furthest1;
            }
            else if ((furthest1-closest1+1)==2)
            {
                for (l=closest1; l<=furthest1-1; l++)
                    config[l]='R';
                config[furthest1]='L';
                while (j<=m && f[j]<=s[furthest1])
                {
                    done[j]=1;
                    j++;
                }
                while (j<=m && f[j]<=s[furthest1-1]+k)
                {
                    done[j]=1;
                    j++;
                }
                last=furthest1;
            }
            else if ((furthest1-closest1+1)>2)
            {
                for (l=closest1; l<=furthest1-2; l++)
                    config[l]='R';
                config[furthest1-1]='L';
                config[furthest1]='R';
                while (j<=m && f[j]<=s[furthest1])
                {
                    done[j]=1;
                    j++;
                }
                while (j<=m && f[j]<=s[furthest1]+k)
                {
                    done[j]=1;
                    j++;
                }
                last=furthest1;
            }
        }
    }
    ls.clear();
    rs.clear();
    for (i=1; i<=n; i++)
    {
        if (config[i]=='L')
            ls.push_back(s[i]);
        else
            rs.push_back(s[i]);
    }
    oke=true;
    for (i=1; i<=m; i++)
    {
        r=-1;
        pas=(1<<16);
        while (pas)
        {
            if (r+pas<rs.size() && rs[r+pas]<=f[i])
                r+=pas;
            pas=pas/2;
        }
        if (r==-1 || rs[r]+k<f[i])
        {
            r=-1;
            pas=(1<<16);
            while (pas)
            {
                if (r+pas<ls.size() && ls[r+pas]<f[i])
                    r+=pas;
                pas=pas/2;
            }
            r++;
            if (r>=ls.size() || ls[r]>f[i] && ls[r]-k>f[i] || ls[r]<f[i])
                oke=false;
        }
    }
    if (oke)
        bigmeeks=config;
    return oke;
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i,j,cnt,r,pas;
    cin >> n >> m;
    for (i=1; i<=n; i++)
        cin >> s[i];
    for (i=1; i<=m; i++)
        cin >> f[i];
    cnt=1;
    s[n+1]=1e9+10;
    s[0]=-1e9;
    for (i=1; i<=n+1; i++)
    {
        if (s[i]!=s[i-1] && !is_between(s[i-1],s[i]))
        {
            cnt++;
            groupstart[cnt]=i;
        }
        if (i<=n)
        {
            group[i]=cnt;
            groupend[cnt]=i;
            groupsz[cnt]++;
        }
    }
    if (!ok(1e9))
    {
        cout << "-1";
    }
    else
    {
        r=0;
        pas=(1<<30);
        while(pas)
        {
            if (!ok(r+pas))
                r+=pas;
            pas=pas/2;
        }
        if (!ok(r))
            r++;
        ok(r);///stiu ca e cringe da na
        cout << r << "\n";
        for (i=1; i<=n; i++)
            cout << bigmeeks[i];
    }
    return 0;
}

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