Submission #1065316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065316		Dan4Life	Sprinklers (CEOI24_sprinklers)	C++17	100 / 100	73 ms	4696 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a), end(a)
using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
const int mxN = (int)1e5+10;
const int INF = (int)2e9+10;
int n, m;
ar2 p[mxN];
string ans;
int f[mxN], s[mxN], dp[mxN];

bool chk(int d){
	int j = 1, k = 1, l = 1;
	for(int i = 1; i <= n; i++){
		if(f[dp[i-1]+1]<s[i]-d) return 0;
		while(j<=m and f[j]<=s[i]+d) j++;
		while(k<=m and f[k]<=s[i]) k++;
		while(l<=m and i>1 and f[l]<=s[i-1]+d) l++;
		if(f[dp[i-1]+1]>=s[i]) dp[i]=j-1, p[i]={1,1};
		else dp[i]=k-1, p[i]={1,0};
		if(i>1 and f[dp[i-2]+1]>=s[i]-d)
			if(dp[i]<l) dp[i]=l-1, p[i]={2,0};
	}
	return dp[n]==m;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> s[i], ans+='L';
	for(int i = 1; i <= m; i++) cin >> f[i]; f[m+1]=INF;
	int l = 0, r = (int)1e9;
	while(l<r){
		int mid = (l+r)/2;
		if(chk(mid)) r=mid;
		else l=mid+1;
	}
	if(!chk(l)){cout<<-1<<"\n";return 0;}
	cout << l << "\n";
	for(int i = n; i; i--){
		if(p[i][0]==2) ans[i-1]='L',ans[i-2]='R', i--;
		else ans[i-1]="LR"[p[i][1]];
	}
	cout << ans << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:35:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   35 |  for(int i = 1; i <= m; i++) cin >> f[i]; f[m+1]=INF;
      |  ^~~
Main.cpp:35:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   35 |  for(int i = 1; i <= m; i++) cin >> f[i]; f[m+1]=INF;
      |                                           ^

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