# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1039587 |
2024-07-31T04:59:45 Z |
정희우(#10993) |
Sprinklers (CEOI24_sprinklers) |
C++17 |
|
232 ms |
3364 KB |
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using lint = long long;
using intp = pair<int,int>;
using vint = vector<int>;
const int MAX_N=100010;
const int MAX_D=1000000010;
int n,m;
int sarr[MAX_N],farr[MAX_N];
int ll[MAX_N],lr[MAX_N],rl[MAX_N],rr[MAX_N];
int dt[MAX_N];
char ans[MAX_N];
bool solve(int d)
{
for(int i=0;i<n;i++)
{
ll[i]=lower_bound(farr,farr+m,sarr[i]-d)-farr;
rr[i]=upper_bound(farr,farr+m,sarr[i]+d)-farr;
}
fill(dt,dt+n+1,0);
for(int i=0;i<n;i++)
{
if(dt[i]>=rl[i])dt[i+1]=max(dt[i+1],rr[i]);
if(i<n-1 && dt[i]>=ll[i+1])dt[i+2]=max(dt[i+2],rr[i]);
if(dt[i]>=ll[i])dt[i+1]=max(dt[i+1],lr[i]);
else return false;
}
return dt[n]==m;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i=0;i<n;i++)
cin >> sarr[i];
for(int i=0;i<m;i++)
cin >> farr[i];
m=unique(farr,farr+m)-farr;
for(int i=0;i<n;i++)
{
lr[i]=upper_bound(farr,farr+m,sarr[i])-farr;
rl[i]=lower_bound(farr,farr+m,sarr[i])-farr;
}
int lb=1,ub=MAX_D;
while(lb<ub)
{
int d=(lb+ub)/2;
if(solve(d))ub=d;
else lb=d+1;
}
if(lb==MAX_D)
{
cout << -1;
return 0;
}
solve(lb);
for(int i=n;i>0;)
{
if(dt[i]==rr[i-1] && dt[i-1]>=rl[i-1])
ans[--i]='R';
else if(i>1 && dt[i]==rr[i-2] && dt[i-2]>=ll[i-1])
{
ans[--i]='L';
ans[--i]='R';
}
else
ans[--i]='L';
}
cout << lb << '\n' << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct |
2 |
Correct |
8 ms |
604 KB |
Correct |
3 |
Correct |
0 ms |
348 KB |
Correct |
4 |
Correct |
6 ms |
688 KB |
Correct |
5 |
Correct |
7 ms |
2648 KB |
Correct |
6 |
Correct |
0 ms |
344 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
1 ms |
348 KB |
Correct |
9 |
Correct |
0 ms |
2396 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Correct |
2 |
Correct |
10 ms |
2696 KB |
Correct |
3 |
Correct |
16 ms |
604 KB |
Correct |
4 |
Correct |
180 ms |
3364 KB |
Correct |
5 |
Correct |
192 ms |
3164 KB |
Correct |
6 |
Correct |
0 ms |
344 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
99 ms |
3180 KB |
Correct |
9 |
Correct |
100 ms |
3160 KB |
Correct |
10 |
Correct |
117 ms |
3164 KB |
Correct |
11 |
Correct |
59 ms |
2988 KB |
Correct |
12 |
Correct |
80 ms |
2908 KB |
Correct |
13 |
Correct |
141 ms |
3048 KB |
Correct |
14 |
Correct |
154 ms |
3068 KB |
Correct |
15 |
Correct |
162 ms |
3072 KB |
Correct |
16 |
Correct |
129 ms |
3156 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Correct |
0 ms |
2392 KB |
Correct |
4 |
Correct |
0 ms |
2396 KB |
Correct |
5 |
Correct |
0 ms |
348 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
0 ms |
348 KB |
Correct |
9 |
Correct |
0 ms |
348 KB |
Correct |
10 |
Correct |
1 ms |
2396 KB |
Correct |
11 |
Correct |
0 ms |
424 KB |
Correct |
12 |
Correct |
0 ms |
344 KB |
Correct |
13 |
Correct |
0 ms |
348 KB |
Correct |
14 |
Correct |
0 ms |
360 KB |
Correct |
15 |
Correct |
0 ms |
348 KB |
Correct |
16 |
Correct |
0 ms |
348 KB |
Correct |
17 |
Correct |
1 ms |
2396 KB |
Correct |
18 |
Correct |
0 ms |
2396 KB |
Correct |
19 |
Correct |
0 ms |
348 KB |
Correct |
20 |
Correct |
0 ms |
2396 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Correct |
2 |
Correct |
39 ms |
1104 KB |
Correct |
3 |
Correct |
232 ms |
3156 KB |
Correct |
4 |
Correct |
221 ms |
3152 KB |
Correct |
5 |
Correct |
225 ms |
3152 KB |
Correct |
6 |
Correct |
228 ms |
3180 KB |
Correct |
7 |
Correct |
227 ms |
3344 KB |
Correct |
8 |
Correct |
225 ms |
3152 KB |
Correct |
9 |
Correct |
208 ms |
3140 KB |
Correct |
10 |
Correct |
221 ms |
3152 KB |
Correct |
11 |
Correct |
222 ms |
3160 KB |
Correct |
12 |
Correct |
0 ms |
348 KB |
Correct |
13 |
Correct |
0 ms |
348 KB |
Correct |
14 |
Incorrect |
58 ms |
2956 KB |
User solution is worse than jury's solution |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Correct |
8 ms |
604 KB |
Correct |
4 |
Correct |
0 ms |
348 KB |
Correct |
5 |
Correct |
6 ms |
688 KB |
Correct |
6 |
Correct |
7 ms |
2648 KB |
Correct |
7 |
Correct |
0 ms |
344 KB |
Correct |
8 |
Correct |
0 ms |
348 KB |
Correct |
9 |
Correct |
1 ms |
348 KB |
Correct |
10 |
Correct |
0 ms |
2396 KB |
Correct |
11 |
Correct |
10 ms |
2696 KB |
Correct |
12 |
Correct |
16 ms |
604 KB |
Correct |
13 |
Correct |
180 ms |
3364 KB |
Correct |
14 |
Correct |
192 ms |
3164 KB |
Correct |
15 |
Correct |
0 ms |
344 KB |
Correct |
16 |
Correct |
0 ms |
348 KB |
Correct |
17 |
Correct |
99 ms |
3180 KB |
Correct |
18 |
Correct |
100 ms |
3160 KB |
Correct |
19 |
Correct |
117 ms |
3164 KB |
Correct |
20 |
Correct |
59 ms |
2988 KB |
Correct |
21 |
Correct |
80 ms |
2908 KB |
Correct |
22 |
Correct |
141 ms |
3048 KB |
Correct |
23 |
Correct |
154 ms |
3068 KB |
Correct |
24 |
Correct |
162 ms |
3072 KB |
Correct |
25 |
Correct |
129 ms |
3156 KB |
Correct |
26 |
Correct |
0 ms |
2392 KB |
Correct |
27 |
Correct |
0 ms |
2396 KB |
Correct |
28 |
Correct |
0 ms |
348 KB |
Correct |
29 |
Correct |
0 ms |
348 KB |
Correct |
30 |
Correct |
0 ms |
348 KB |
Correct |
31 |
Correct |
0 ms |
348 KB |
Correct |
32 |
Correct |
0 ms |
348 KB |
Correct |
33 |
Correct |
1 ms |
2396 KB |
Correct |
34 |
Correct |
0 ms |
424 KB |
Correct |
35 |
Correct |
0 ms |
344 KB |
Correct |
36 |
Correct |
0 ms |
348 KB |
Correct |
37 |
Correct |
0 ms |
360 KB |
Correct |
38 |
Correct |
0 ms |
348 KB |
Correct |
39 |
Correct |
0 ms |
348 KB |
Correct |
40 |
Correct |
1 ms |
2396 KB |
Correct |
41 |
Correct |
0 ms |
2396 KB |
Correct |
42 |
Correct |
0 ms |
348 KB |
Correct |
43 |
Correct |
0 ms |
2396 KB |
Correct |
44 |
Correct |
39 ms |
1104 KB |
Correct |
45 |
Correct |
232 ms |
3156 KB |
Correct |
46 |
Correct |
221 ms |
3152 KB |
Correct |
47 |
Correct |
225 ms |
3152 KB |
Correct |
48 |
Correct |
228 ms |
3180 KB |
Correct |
49 |
Correct |
227 ms |
3344 KB |
Correct |
50 |
Correct |
225 ms |
3152 KB |
Correct |
51 |
Correct |
208 ms |
3140 KB |
Correct |
52 |
Correct |
221 ms |
3152 KB |
Correct |
53 |
Correct |
222 ms |
3160 KB |
Correct |
54 |
Correct |
0 ms |
348 KB |
Correct |
55 |
Correct |
0 ms |
348 KB |
Correct |
56 |
Incorrect |
58 ms |
2956 KB |
User solution is worse than jury's solution |
57 |
Halted |
0 ms |
0 KB |
- |