# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1199052 | BigBadBully | Sprinklers (CEOI24_sprinklers) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define pid pair<int,double>
#define pii pair<int,int>
#define ff first
#define ss second
const int inf = 1e18;
const int maxn = 1e3;
using namespace std;
void solve()
{
int n,m;
cin >> n >> m;
vector<int> va(n),vb(m);
for (int i = 0; i < n; i++)
cin >> va[i];
for (int i = 0; i < m; i++)
cin >> vb[i];
set<int> svn;
for (int x: va)
svn.insert(x);
vector<int> nvb;
for (int i = 0; i < m; i++)
if (!svn.count(vb[i]))
nvb.push_back(vb[i]);
//1 = R
//0 = L
m = nvb.size();
vb = nvb;
string bad = "l";
auto calc = [&](int k)
{
vector<vector<pii>> seg(n);
for (int i = 0; i < m; i++)
{
vector<int> mask;
auto it2 = upper_bound(va.begin(),va.end(),vb[i]+k)-va.begin();
auto it0 = lower_bound(va.begin(),va.end(),vb[i]-k)-va.begin();
auto it1 = lower_bound(va.begin(),va.end(),vb[i])-va.begin();
if (it0 >= n ||it2 == 0)
return 0;
for (int j = it0; j < it1; j++)
mask.push_back(0);
for (int j = it1; j < it2; j++)
mask.push_back(1);
if (count(mask.begin(),mask.end(),0) >= 3)
seg[it2-1].push_back({3,0});
else if (count(mask.begin(),mask.end(),1) >= 3)
seg[it2-1].push_back({3,(1<<3)-1});
else
{
int sum = 0;
int f = mask.size();
for (int j = 0; j < f; j++)
sum+=(1<<f-1-j)*mask[j];
seg[it2-1].push_back({mask.size(),sum});
}
}
array<int,8> prev,nxt;
for (int i = 0; i < 8; i++)
prev[i] = 0;
vector<array<int,8>> dp(n);
for (int i = 0; i < n; i++)
{
array<int,16> cands;
for (int j = 0; j < 8; j++)
cands[2*j] = (prev[j] != -1 ? j : -1),
cands[2*j+1] = (prev[j] != -1 ? j : -1);
for (auto x : seg[i])
for (int cnt = 0; cnt < 16; cnt+=(1<<x.ff))
cands[x.ss+cnt] = -1;
for (int j = 0; j < 8; j++)
prev[j]=(cands[j] != -1 ? cands[j] : cands[j+(1<<3)]);
dp[i] = prev;
}
/*
for (int j = 0; j < 8; j++)
if (prev[j] != -1)
{
string ans;
auto cur = j;
for (int i = n-1; i >= 0; i--)
ans.push_back(cur%2 ? 'R' : 'L'),cur = dp[i][cur];
reverse(ans.begin(),ans.end());
return ans;
}
*/
for (int j = 0; j < 8; j++)
if (prev[j]!=1)
return 1;
return 0;
};
auto calc_s = [&](int k)
{
vector<vector<pii>> seg(n);
for (int i = 0; i < m; i++)
{
vector<int> mask;
auto it2 = upper_bound(va.begin(),va.end(),vb[i]+k)-va.begin();
auto it0 = lower_bound(va.begin(),va.end(),vb[i]-k)-va.begin();
auto it1 = lower_bound(va.begin(),va.end(),vb[i])-va.begin();
for (int j = it0; j < it1; j++)
mask.push_back(0);
for (int j = it1; j < it2; j++)
mask.push_back(1);
if (count(mask.begin(),mask.end(),0) >= 3)
seg[it2-1].push_back({3,0});
else if (count(mask.begin(),mask.end(),1) >= 3)
seg[it2-1].push_back({3,(1<<3)-1});
else
{
int sum = 0;
int f = mask.size();
for (int j = 0; j < f; j++)
sum+=(1<<f-1-j)*mask[j];
seg[it2-1].push_back({mask.size(),sum});
}
}
array<int,8> prev,nxt;
for (int i = 0; i < 8; i++)
prev[i] = 0;
vector<array<int,8>> dp(n);
for (int i = 0; i < n; i++)
{
array<int,16> cands;
for (int j = 0; j < 8; j++)
cands[2*j] = (prev[j] != -1 ? j : -1),
cands[2*j+1] = (prev[j] != -1 ? j : -1);
for (auto x : seg[i])
for (int cnt = 0; cnt < 16; cnt+=(1<<x.ff))
cands[x.ss+cnt] = -1;
for (int j = 0; j < 8; j++)
prev[j]=(cands[j] != -1 ? cands[j] : cands[j+(1<<3)]);
dp[i] = prev;
}
for (int j = 0; j < 8; j++)
if (prev[j] != -1)
{
string ans;
auto cur = j;
for (int i = n-1; i >= 0; i--)
ans.push_back(cur%2 ? 'R' : 'L'),cur = dp[i][cur];
reverse(ans.begin(),ans.end());
return ans;
}
return 0;
};
if (m==0)
{
cout << 0 <<'\n';
cout << string(n,'L') << '\n';
return;
}
int l = 0, r = 1e9;
while(r-l)
{
int mid =l+r>>1;
if (calc(mid))
r = mid;
else
l = mid+1;
}
if (l==1e9)
cout << -1 << endl;
else
cout << l << '\n' << calc_s(l) << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
int t = 1;
//cin >> t;
while(t--)
solve();
}