oj.uz

Submission #1075059

# Submission time Handle Problem Language Result Execution time Memory
1075059 2024-08-25T18:00:01 Z oscar1f Sprinklers (CEOI24_sprinklers) C++17
20 / 100
 2000 ms 54252 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,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];

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 (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);
        arroTri.insert({valNouv,i});
    }
    listeArro.push_back(2*INFINI);
    arroTri.insert({2*INFINI,nbArro+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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 21 ms 8932 KB Correct
3 Correct 0 ms 344 KB Correct
4 Correct 38 ms 13628 KB Correct
5 Correct 38 ms 13628 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 6 ms 2776 KB Correct
9 Correct 0 ms 348 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 35 ms 9688 KB Correct
3 Correct 89 ms 4708 KB Correct
4 Correct 1709 ms 52016 KB Correct
5 Correct 1722 ms 51984 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 1 ms 348 KB Correct
8 Correct 376 ms 23396 KB Correct
9 Correct 432 ms 23804 KB Correct
10 Correct 1297 ms 48164 KB Correct
11 Correct 1459 ms 39108 KB Correct
12 Correct 546 ms 26160 KB Correct
13 Correct 1833 ms 44620 KB Correct
14 Execution timed out 2050 ms 47520 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 1 ms 348 KB Correct
5 Correct 1 ms 604 KB Correct
6 Correct 1 ms 600 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 1 ms 348 KB Correct
9 Correct 1 ms 600 KB Correct
10 Correct 1 ms 604 KB Correct
11 Correct 1 ms 348 KB Correct
12 Correct 1 ms 604 KB Correct
13 Correct 1 ms 604 KB Correct
14 Correct 1 ms 348 KB Correct
15 Correct 1 ms 348 KB Correct
16 Correct 1 ms 348 KB Correct
17 Correct 1 ms 348 KB Correct
18 Correct 0 ms 348 KB Correct
19 Correct 1 ms 600 KB Correct
20 Correct 1 ms 604 KB Correct

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 224 ms 11968 KB Correct
3 Execution timed out 2057 ms 54252 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 21 ms 8932 KB Correct
4 Correct 0 ms 344 KB Correct
5 Correct 38 ms 13628 KB Correct
6 Correct 38 ms 13628 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 6 ms 2776 KB Correct
10 Correct 0 ms 348 KB Correct
11 Correct 35 ms 9688 KB Correct
12 Correct 89 ms 4708 KB Correct
13 Correct 1709 ms 52016 KB Correct
14 Correct 1722 ms 51984 KB Correct
15 Correct 0 ms 348 KB Correct
16 Correct 1 ms 348 KB Correct
17 Correct 376 ms 23396 KB Correct
18 Correct 432 ms 23804 KB Correct
19 Correct 1297 ms 48164 KB Correct
20 Correct 1459 ms 39108 KB Correct
21 Correct 546 ms 26160 KB Correct
22 Correct 1833 ms 44620 KB Correct
23 Execution timed out 2050 ms 47520 KB Time limit exceeded
24 Halted 0 ms 0 KB -