oj.uz

Submission #1074992

# Submission time Handle Problem Language Result Execution time Memory
1074992 2024-08-25T17:21:25 Z oscar1f Sprinklers (CEOI24_sprinklers) C++17
20 / 100
 2000 ms 46568 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({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;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

# 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

Subtask #2
0.0 / 6.0

# 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 -

Subtask #3
17.0 / 17.0

# 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

Subtask #4
0.0 / 27.0

# 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 -

Subtask #5
0.0 / 47.0

# 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 -