Submission #1319464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319464		HoriaHaivas	Sprinklers (CEOI24_sprinklers)	C++20	0 / 100	13 ms	2628 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 group[100005];
int groupend[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,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)
        {
            bound=groupend[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;
        }
    }
    string config;
    config="$";
    for (i=1; i<=n; i++)
        config+='R';
    for (i=1; i<=m; i++)
        done[i]=0;
    j=1;
    last=0;
    for (i=1;i<=m;i++)
    {
         if (!done[i])
         {
             furthest1=furthest[i];
             if (furthest1==n+1)
                 continue;
             if (groupsz[group[furthest1]]==1)
             {
                 for (l=last+1;l<=furthest1;l++)
                      config[l]='L';
                 while (j<=m && f[j]<=s[furthest1])
                 {
                     done[j]=1;
                     j++;
                 }
                 last=furthest1;
             }
             else if (groupsz[group[furthest1]]==2)
             {
                 for (l=last+1;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 (groupsz[group[furthest1]]>2)
             {
                 for (l=last+1;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;
    group[1]=cnt;
    groupend[1]=1;
    groupsz[cnt]++;
    for (i=2; i<=n; i++)
    {
        if (!is_between(s[i],s[i-1]))
        {
            cnt++;
        }
        group[i]=cnt;
        groupend[i]=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;
        }
        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: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47