Submission #1075264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075264		oscar1f	Sprinklers (CEOI24_sprinklers)	C++17	100 / 100	1749 ms	55972 KiB

Main

#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,arroTri;
unordered_map<int,int> dejaArro;
unordered_map<int,int> memo,dv,proFleur;
unordered_map<int,char> direc;
int suivGau[TAILLE_MAX],suivDro[TAILLE_MAX],premAp[TAILLE_MAX],premAv[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 or pos>premAp[fleurPb]+2) {
        return 0;
    }
    int caseTab=pos*INFINI+fleurPb;
    if (dv[caseTab]!=0) {
        return memo[caseTab];
    }
    dv[caseTab]=1;
    if (listeArro[pos-1]<listeFleur[fleurPb]) {
        if (premAv[fleurPb]>pos) {
            memo[caseTab]=dyna(premAv[fleurPb],fleurPb);
            return memo[caseTab];
        }
        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;
    }
    for (int i=0;i<nbFleur;i++) {
        it=arroTri.lower_bound({listeFleur[i],0});
        it--;
        premAv[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=max(proFleur[caseTab],fleurPb);
    }
    //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);
        arroTri.insert({valNouv,i});
    }
    listeArro.push_back(2*INFINI);
    arroTri.insert({2*INFINI,nbArro+1});
    arroTri.insert({-2*INFINI,-1});
    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});
    set<pair<int,int>>::iterator it;
    for (int i=0;i<nbFleur;i++) {
        it=arroTri.lower_bound({listeFleur[i],INFINI});
        premAp[i]=(*it).second;
    }

    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;
}
 

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