oj.uz

Submission #1074985

# Submission time Handle Problem Language Result Execution time Memory
1074985 2024-08-25T17:18:52 Z oscar1f Sprinklers (CEOI24_sprinklers) C++17
3 / 100
 63 ms 15648 KB 
#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({INFINI,nbFleur});
    fleurTri.insert({-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;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 33 ms 7464 KB Correct
3 Correct 1 ms 348 KB Correct
4 Correct 63 ms 11776 KB Correct
5 Correct 38 ms 11788 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 8 ms 2520 KB Correct
9 Correct 1 ms 348 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Runtime error 46 ms 15648 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Runtime error 51 ms 14964 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 33 ms 7464 KB Correct
4 Correct 1 ms 348 KB Correct
5 Correct 63 ms 11776 KB Correct
6 Correct 38 ms 11788 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 8 ms 2520 KB Correct
10 Correct 1 ms 348 KB Correct
11 Runtime error 46 ms 15648 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -