#include<bits/stdc++.h>
using namespace std;
#define int long long
const int TAILLE_MAX=100*1000+5,INFINI=1000*1000*1000+5;
int nbArro,nbFleur,tailleInter;
vector<int> listeArro,listeFleur;
set<pair<int,int>> fleurTri;
unordered_map<int,int> dejaArro;
unordered_map<int,int> memo,dv,proFleur;
unordered_map<int,char> direc;
int suivGau[TAILLE_MAX],suivDro[TAILLE_MAX];
void afficher(vector<int> v) {
for (int i:v) {
cout<<i<<" ";
}
cout<<endl;
}
int dyna(int pos,int fleurPb) {
if (fleurPb==nbFleur) {
return 1;
}
if (pos>nbArro) {
return 0;
}
int caseTab=pos*INFINI+fleurPb;
if (dv[caseTab]!=0) {
return memo[caseTab];
}
dv[caseTab]=1;
if (listeArro[pos-1]<listeFleur[fleurPb]) {
if (listeArro[pos]<listeFleur[fleurPb]) {
memo[caseTab]=dyna(pos+1,suivDro[pos]);
proFleur[caseTab]=suivDro[pos];
direc[caseTab]='R';
}
else if (listeArro[pos]-tailleInter>listeFleur[fleurPb]) {
memo[caseTab]=0;
}
else {
if (dyna(pos+1,fleurPb)==1) {
memo[caseTab]=1;
proFleur[caseTab]=fleurPb;
direc[caseTab]='R';
}
else if (dyna(pos+1,suivGau[pos])==1) {
memo[caseTab]=1;
proFleur[caseTab]=suivGau[pos];
direc[caseTab]='L';
}
}
}
else {
if (listeArro[pos]-tailleInter>listeFleur[fleurPb]) {
memo[caseTab]=0;
}
else {
if (dyna(pos+1,fleurPb)==1) {
memo[caseTab]=1;
proFleur[caseTab]=fleurPb;
direc[caseTab]='R';
}
else if (dyna(pos+1,max(suivGau[pos],suivDro[pos-1]))==1) {
memo[caseTab]=1;
proFleur[caseTab]=max(suivGau[pos],suivDro[pos-1]);
direc[caseTab]='L';
}
}
}
return memo[caseTab];
}
pair<bool,string> verif(int valQuest) {
tailleInter=valQuest;
memo.clear();
dv.clear();
proFleur.clear();
direc.clear();
set<pair<int,int>>::iterator it;
for (int i=0;i<=nbArro;i++) {
it=fleurTri.lower_bound({listeArro[i],2*INFINI});
suivGau[i]=(*it).second;
it=fleurTri.lower_bound({listeArro[i]+tailleInter,2*INFINI});
suivDro[i]=(*it).second;
}
if (dyna(1,0)==0) {
return {false,""};
}
string ans;
//cout<<tailleInter<<" : ";
int fleurPb=0,caseTab;
for (int i=1;i<=nbArro;i++) {
caseTab=i*INFINI+fleurPb;
//cout<<i<<" "<<fleurPb<<" "<<direc[caseTab]<<endl;
if (direc[caseTab]!=(char)0) {
ans+=direc[caseTab];
}
else {
ans+='L';
}
fleurPb=proFleur[caseTab];
}
//cout<<ans<<endl;
return {true,ans};
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>nbArro>>nbFleur;
int valNouv;
listeArro.push_back(-2*INFINI);
for (int i=0;i<nbArro;i++) {
cin>>valNouv;
dejaArro[valNouv]=1;
listeArro.push_back(valNouv);
}
listeArro.push_back(2*INFINI);
int numFleur=0;
for (int i=0;i<nbFleur;i++) {
cin>>valNouv;
if (dejaArro[valNouv]==0) {
listeFleur.push_back(valNouv);
fleurTri.insert({valNouv,numFleur});
dejaArro[valNouv]=1;
numFleur++;
}
}
//afficher(listeFleur);
if (listeFleur.empty()) {
cout<<0<<endl;
for (int i=0;i<nbArro;i++) {
cout<<'L';
}
cout<<endl;
return 0;
}
nbFleur=listeFleur.size();
fleurTri.insert({5*INFINI,nbFleur});
fleurTri.insert({-5*INFINI,-1});
int debDicho=0,finDicho=INFINI,midDicho;
while (debDicho!=finDicho) {
midDicho=(debDicho+finDicho)/2;
if (verif(midDicho).first) {
finDicho=midDicho;
}
else {
debDicho=midDicho+1;
}
}
if (debDicho==INFINI) {
cout<<-1<<endl;
}
else {
cout<<debDicho<<endl;
cout<<verif(debDicho).second<<endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct |
2 |
Correct |
1 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct |
2 |
Correct |
23 ms |
7640 KB |
Correct |
3 |
Correct |
0 ms |
344 KB |
Correct |
4 |
Correct |
41 ms |
11836 KB |
Correct |
5 |
Correct |
38 ms |
11832 KB |
Correct |
6 |
Correct |
0 ms |
344 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
9 ms |
2436 KB |
Correct |
9 |
Correct |
0 ms |
352 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct |
2 |
Correct |
40 ms |
7892 KB |
Correct |
3 |
Correct |
84 ms |
3672 KB |
Correct |
4 |
Correct |
1614 ms |
41500 KB |
Correct |
5 |
Correct |
1669 ms |
41584 KB |
Correct |
6 |
Correct |
0 ms |
344 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
951 ms |
32300 KB |
Correct |
9 |
Correct |
648 ms |
32624 KB |
Correct |
10 |
Execution timed out |
2100 ms |
46568 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct |
2 |
Correct |
1 ms |
348 KB |
Correct |
3 |
Correct |
0 ms |
344 KB |
Correct |
4 |
Correct |
1 ms |
348 KB |
Correct |
5 |
Correct |
1 ms |
348 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
1 ms |
348 KB |
Correct |
9 |
Correct |
1 ms |
604 KB |
Correct |
10 |
Correct |
1 ms |
468 KB |
Correct |
11 |
Correct |
1 ms |
344 KB |
Correct |
12 |
Correct |
1 ms |
348 KB |
Correct |
13 |
Correct |
1 ms |
348 KB |
Correct |
14 |
Correct |
0 ms |
348 KB |
Correct |
15 |
Correct |
1 ms |
348 KB |
Correct |
16 |
Correct |
0 ms |
348 KB |
Correct |
17 |
Correct |
1 ms |
344 KB |
Correct |
18 |
Correct |
1 ms |
344 KB |
Correct |
19 |
Correct |
0 ms |
348 KB |
Correct |
20 |
Correct |
1 ms |
344 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct |
2 |
Correct |
194 ms |
9692 KB |
Correct |
3 |
Correct |
1993 ms |
44776 KB |
Correct |
4 |
Execution timed out |
2080 ms |
45048 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct |
2 |
Correct |
1 ms |
348 KB |
Correct |
3 |
Correct |
23 ms |
7640 KB |
Correct |
4 |
Correct |
0 ms |
344 KB |
Correct |
5 |
Correct |
41 ms |
11836 KB |
Correct |
6 |
Correct |
38 ms |
11832 KB |
Correct |
7 |
Correct |
0 ms |
344 KB |
Correct |
8 |
Correct |
0 ms |
348 KB |
Correct |
9 |
Correct |
9 ms |
2436 KB |
Correct |
10 |
Correct |
0 ms |
352 KB |
Correct |
11 |
Correct |
40 ms |
7892 KB |
Correct |
12 |
Correct |
84 ms |
3672 KB |
Correct |
13 |
Correct |
1614 ms |
41500 KB |
Correct |
14 |
Correct |
1669 ms |
41584 KB |
Correct |
15 |
Correct |
0 ms |
344 KB |
Correct |
16 |
Correct |
0 ms |
348 KB |
Correct |
17 |
Correct |
951 ms |
32300 KB |
Correct |
18 |
Correct |
648 ms |
32624 KB |
Correct |
19 |
Execution timed out |
2100 ms |
46568 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |