Submission #1094538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094538		epicci23	Sprinklers (CEOI24_sprinklers)	C++17	53 / 100	99 ms	6028 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;


int n,m;
vector<int> a,b;

void _(){
  cin >> n >> m;
  for(int i=0;i<n;i++){
  	int x; cin >> x;
  	a.push_back(x);
  }
  for(int i=0;i<m;i++){
  	int x;cin >> x;
  	b.push_back(x);
  }

  auto check = [&](int pow)->pair<bool,vector<char>>{

    int p=0;
    vector<char> res(n,'L');

    for(int i=0;i<m;){

      if(p==n) return {0,res};
      int lol=-1;
      while(p<n && a[p]<=b[i]){
        res[p]='R';
        lol=max(lol,a[p]+pow);
        p++;
      }

      if(lol>=b[i]){
       while(i<m && lol>=b[i]) i++;
       continue;
      }

      if(i==m) return {1,res};
      if(p==n) return {0,res};
      
      vector<int> f; 
      while(p<n && a[p]-pow<=b[i]) f.push_back(p++);

      if(sz(f)==0) return {0,res};

      if(sz(f)==1){
        while(i<m && b[i]<=a[f[0]]) i++;
        continue;
      }

      if(sz(f)>=3){
        for(int j=0;j<sz(f);j++){
          if(j==sz(f)-2) continue;
          res[f[j]]='R';
        }
        while(i<m && b[i]<=a[f.back()]+pow) i++;
        continue;
      }

      while(i<m && b[i]<=a[f[0]]) i++;
      if(i==m) return {1,res};
      if(b[i]>=a[f[1]]){
        p--;
        continue;
      }
      else{
        res[f[0]]='R';
        while(i<m && b[i]<=a[f[0]]+pow) i++;
      }
    }
    return {1,res};
  };

  auto check2 = [&](int pow)->pair<bool,vector<char>>{
    int p=n-1;
    vector<char> res(n,'R');

    for(int i=m-1;i>=0;){

      if(p<0) return {0,res};
      int lol=(int)1e18;
      while(p>=0 && a[p]>=b[i]){
        res[p]='L';
        lol=min(lol,a[p]-pow);
        p--;
      }

      if(lol<=b[i]){
       while(i>=0 && lol<=b[i]) i--;
       continue;
      }

      if(i<0) return {1,res};
      if(p<0) return {0,res};
      
      vector<int> f; 
      while(p>=0 && a[p]+pow>=b[i]) f.push_back(p--);

      if(sz(f)==0) return {0,res};

      if(sz(f)==1){
        while(i>=0 && b[i]>=a[f[0]]) i--;
        continue;
      }

      if(sz(f)>=3){
        for(int j=0;j<sz(f);j++){
          if(j==sz(f)-2) continue;
          res[f[j]]='L';
        }
        while(i>=0 && b[i]>=a[f.back()]-pow) i--;
        continue;
      }

      while(i>=0 && b[i]>=a[f[0]]) i--;
      if(i<0) return {1,res};
      
      if(b[i]<=a[f[1]]){
        p++;
        continue;
      }
      else{
        res[f[0]]='L';
        while(i>=0 && b[i]>=a[f[0]]-pow) i--;
      }
    }
    return {1,res};
  };


  int l=0,r=(int)1e18;
  while(l<r){
    int m=(l+r)/2;
    if(check(m).first || check2(m).first) r=m;
    else l=m+1;
  }  
  if(r==(int)1e18) cout << -1 << '\n';
  else if(check2(m).first){
    auto X = check2(l);
    cout << l << '\n';
    for(char x:X.second) cout << x;
    cout << '\n';
  }
  else{
    auto X = check(l);
    cout << l << '\n';
    for(char x:X.second) cout << x;
    cout << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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