#include <bits/stdc++.h>
using namespace std;
int S, F;
int kMin, kMax;
vector<int> sprink;
vector<int> fleurs;
int dernier;
deque<int> poss;
int possibleS[100000+42];
int possibleF[100000+42];
bool directions[100000+42];
int parQui[100000+42];
int parQuiMin[100000+42];
int val(int a, int b)
{
if (!b) return fleurs[a];
return sprink[a];
}
struct objet
{
int pos;
int typ;
bool operator<(const objet &autre) const
{
if (val(pos,typ) == val(autre.pos, autre.typ)) return typ < autre.typ;
return val(pos,typ) < val(autre.pos, autre.typ);
}
};
vector<objet> fusion;
bool tester(int k)
{
for (int i = 0; i < F; i ++)
{
parQui[i] = -1;
}
for (int i = 0; i < S; i ++)
{
possibleS[i] = 0;
}
for (int i = 0; i < F; i ++)
{
possibleF[i] = 0;
}
dernier=-1;
poss.clear();
for (int i = fusion.size()-1; i >=0; i --)
{
int endr = val(fusion[i].pos, fusion[i].typ);
int sorte = fusion[i].typ;
int ind = fusion[i].pos;
if (sorte == 1)
{
auto ans = upper_bound(fleurs.begin(), fleurs.end(), endr + k);
if (ans == fleurs.end())
{
possibleS[fusion[i].pos] = true;
}
else if (sprink[ind+1] <= fleurs[ans-fleurs.begin()])
{
possibleS[ind] = possibleS[ind+1];
}
else
{
possibleS[fusion[i].pos] = possibleF[ans - fleurs.begin()];
}
if (ind != S-1 && sprink[ind+1] <= sprink[ind]+k)
{
poss.push_back(ind+1);
}
dernier = fusion[i].pos;
}
if (sorte == 0)
{
while (!poss.empty() && sprink[poss.front()] > endr + k)
{
poss.pop_front();
}
if (dernier != -1)
{
if (sprink[dernier] <= endr+k)
{
auto ans = upper_bound(fleurs.begin(), fleurs.end(), sprink[dernier]);
if (ans == fleurs.end() || possibleF[ans-fleurs.begin()])
{
possibleF[ind] = true;
parQui[ind] = dernier;
}
}
}
if (!poss.empty())
{
possibleF[ind]= possibleS[poss[0]];
if (possibleF[ind]) parQui[ind] = poss[0];
}
}
}
if (fusion[0].typ == 0) return possibleF[0];
return possibleS[0];
}
int main()
{
cin >> S >> F;
sprink.resize(S);
fleurs.resize(F);
fusion.resize(S+F);
for (int i = 0; i < S; i ++) {cin >> sprink[i]; fusion[i] = {i,1};}
int position = 0;
int vF=F;
for (int i = 0; i <vF; i ++)
{
cin >> fleurs[position];
auto dans = lower_bound(sprink.begin(), sprink.end(), fleurs[position]);
if ((dans == sprink.end() || *dans != fleurs[position]) && (position == 0 || fleurs[position] != fleurs[position-1]))
{
fusion[position+S]={position, 0};
position++;
}
else F--;
}
fusion.resize(S+F);
fleurs.resize(F);
sort(fusion.begin(), fusion.end());
kMin = 0;
kMax = 1e9+10;
while (kMin < kMax)
{
int k = kMin + (kMax-kMin)/2;
if (tester(k))
{
kMax = k;
for (int i = 0; i < F; i ++) parQuiMin[i] = parQui[i];
}
else
{
kMin = k+1;
}
}
if (kMin> 1e9)
{
cout << "-1\n";
return 0;
}
cout << kMin << "\n";
for (int i = 0; i < S; i ++)
{
directions[parQuiMin[i]] = 1;
}
for (int i = 0; i < S; i ++)
{
directions[i] ? cout << 'L' : cout << 'R';
}
cout << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct |
2 |
Correct |
50 ms |
2980 KB |
Correct |
3 |
Correct |
1 ms |
348 KB |
Correct |
4 |
Correct |
45 ms |
3144 KB |
Correct |
5 |
Correct |
56 ms |
3164 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
13 ms |
1032 KB |
Correct |
9 |
Correct |
0 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Incorrect |
63 ms |
3364 KB |
User solution is worse than jury's solution |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Incorrect |
1 ms |
352 KB |
User solution is incorrect |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Incorrect |
96 ms |
3264 KB |
User solution is incorrect |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
348 KB |
Correct |
3 |
Correct |
50 ms |
2980 KB |
Correct |
4 |
Correct |
1 ms |
348 KB |
Correct |
5 |
Correct |
45 ms |
3144 KB |
Correct |
6 |
Correct |
56 ms |
3164 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
0 ms |
348 KB |
Correct |
9 |
Correct |
13 ms |
1032 KB |
Correct |
10 |
Correct |
0 ms |
348 KB |
Correct |
11 |
Incorrect |
63 ms |
3364 KB |
User solution is worse than jury's solution |
12 |
Halted |
0 ms |
0 KB |
- |