Submission #1074962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074962		oscar1f	Sprinklers (CEOI24_sprinklers)	C++17	0 / 100	32 ms	21464 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;
unordered_map<int,int> dejaArro;
unordered_map<int,int> memo,dv,proFleur;
unordered_map<int,char> direc;
int suivGau[TAILLE_MAX],suivDro[TAILLE_MAX];

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;
    int fleurPb=1,caseTab;
    for (int i=1;i<=nbArro;i++) {
        caseTab=i*INFINI+fleurPb;
        if (direc[caseTab]!=(char)0) {
            ans+=direc[caseTab];
        }
        else {
            ans+='L';
        }
        fleurPb=proFleur[caseTab];
    }
    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});
            numFleur++;
        }
    }
    fleurTri.insert({INFINI,nbFleur});
    fleurTri.insert({-INFINI,-1});
    if (listeFleur.empty()) {
        cout<<0<<endl;
        for (int i=0;i<nbArro;i++) {
            cout<<'L';
        }
        cout<<endl;
        return 0;
    }
    nbFleur=listeFleur.size();
    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(midDicho).second<<endl;
    }
    return 0;
}
 

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