Submission #1140546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140546		KaleemRazaSyed	Sprinklers (CEOI24_sprinklers)	C++20	26 / 100	558 ms	5896 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int s[N], f[N], n, m;

bool cover(vector<pair<int,int> > R)
{
  sort(R.begin(), R.end());

  multiset<int> rs;
  int j = 0;
  for(int i = 0; i < m; i++)
    {
      while(j < R.size() && R[j].first <= f[i])
	rs.insert(R[j].second), j++;

      while(rs.size() && *rs.begin() < f[i]) rs.erase(rs.begin());

      if(rs.empty()) return false;
    }
  return true;
}

vector<char> create(int x)
{
  vector<char> sol;
  if(n <= 10)
    {
      for(int mask = 0; mask < (1 << n); mask++)
	{ // 0 means left, 1 means right

	  vector<pair<int,int> > ranges(n);
	  for(int i = 0; i < n; i ++)
	    if((1 << i) & mask)
	      ranges[i] = {s[i], s[i] + x};
	    else
	      ranges[i] = {s[i] - x, s[i]};

	  if(cover(ranges))
	    {
	      sol.resize(n);
	      for(int i = 0; i < n; i ++)
		if((1 << i) & mask)
		  sol[i] = 'R';
		else
		  sol[i]  = 'L';
	      break;
	    }
	}
      return sol;
    }
  else
    {
      vector<pair<int,int> > ranges(n);
      for(int i = 0; i < n; i ++)
	if(i % 3 == 0)
	  ranges[i] = {s[i], s[i] + x};
	else
	  ranges[i] = {s[i] - x, s[i]};

      if(cover(ranges))
	{
	  sol.resize(n);
	  for(int i  = 0; i < n; i ++)
	    if(i % 3 == 0)
	      sol[i] = 'R';
	    else
	      sol[i] = 'L';
	}
    }
  return sol;
}

bool check(int x) {
  vector<char> sol = create(x);
  return sol.size();
}

int main()
{
  cin >> n >> m;
  
  for(int i = 0; i < n; i ++)
    cin >> s[i];

  for(int i = 0; i < m; i++)
    cin >> f[i];

  const int inf = 1e9 + 10;
  int l = -1, r = inf;

  while(r - l > 1)
    {
      int mid = (l + r) / 2;
      if(check(mid))
	r = mid;
      else
	l = mid;
    }
  
  cout << (r == inf ? -1 : r) << endl;

  vector<char> sol = create(r);
  for(char i : sol)
    cout << i;
  cout << endl;
  
  return 0;
}

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