Submission #1063602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063602		oscar1f	Sparklers (JOI17_sparklers)	C++17	100 / 100	278 ms	17028 KiB

sparklers

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int TAILLE_MAX=100*1000+5,INFINI=1000*1000*1000;
int nbVal,posInit,tempsInit;
int val[TAILLE_MAX];

void afficher(vector<int> v) {
    for (int i:v) {
        cout<<i<<" ";
    }
    cout<<endl;
}

vector<int> calcCumu(vector<int> v) {
    vector<int> ans={0};
    int somCour=0;
    for (int i:v) {
        somCour+=i;
        ans.push_back(somCour);
    }
    return ans;
}

bool verif(int temps) {
    //cout<<temps<<endl;
    vector<int> listeGau,listeDro;
    for (int i=posInit;i>1;i--) {
        listeGau.push_back(2*temps-val[i]+val[i-1]);
    }
    for (int i=posInit+1;i<=nbVal;i++) {
        listeDro.push_back(2*temps-val[i]+val[i-1]);
    }
    vector<int> cumuGau=calcCumu(listeGau),cumuDro=calcCumu(listeDro);
    //afficher(cumuGau);
    //afficher(cumuDro);
    int tailleGau=cumuGau.size(),tailleDro=cumuDro.size();
    /*for (int i:cumuGau) {
        for (int j:cumuDro) {
            if (i+j>=0) {
                cout<<1<<" ";
            }
            else {
                cout<<0<<" ";
            }
        }
        cout<<endl;
    } 
    cout<<endl;*/
    int minCour=INFINI*INFINI,maxCour=-INFINI*INFINI,posMin=0,posMax=0;
    vector<pair<int,int>> minJusquaGau,maxJusquaGau,minDepuisGau,maxDepuisGau;
    for (int i=0;i<tailleGau;i++) {
        if (minCour>cumuGau[i]) {
            minCour=cumuGau[i];
            posMin=i;
        }
        if (maxCour<cumuGau[i]) {
            maxCour=cumuGau[i];
            posMax=i;
        }
        minJusquaGau.push_back({minCour,posMin});
        maxJusquaGau.push_back({maxCour,posMax});
    }
    minCour=INFINI*INFINI;
    maxCour=-INFINI*INFINI;
    for (int i=tailleGau-1;i>=0;i--) {
        if (minCour>cumuGau[i]) {
            minCour=cumuGau[i];
            posMin=i;
        }
        if (maxCour<cumuGau[i]) {
            maxCour=cumuGau[i];
            posMax=i;
        }
        minDepuisGau.push_back({minCour,posMin});
        maxDepuisGau.push_back({maxCour,posMax});
    }
    reverse(minDepuisGau.begin(),minDepuisGau.end());
    reverse(maxDepuisGau.begin(),maxDepuisGau.end());

    minCour=INFINI*INFINI;
    maxCour=-INFINI*INFINI;
    vector<pair<int,int>> minJusquaDro,maxJusquaDro,minDepuisDro,maxDepuisDro;
    for (int i=0;i<tailleDro;i++) {
        if (minCour>cumuDro[i]) {
            minCour=cumuDro[i];
            posMin=i;
        }
        if (maxCour<cumuDro[i]) {
            maxCour=cumuDro[i];
            posMax=i;
        }
        minJusquaDro.push_back({minCour,posMin});
        maxJusquaDro.push_back({maxCour,posMax});
    }
    minCour=INFINI*INFINI;
    maxCour=-INFINI*INFINI;
    for (int i=tailleDro-1;i>=0;i--) {
        if (minCour>cumuDro[i]) {
            minCour=cumuDro[i];
            posMin=i;
        }
        if (maxCour<cumuDro[i]) {
            maxCour=cumuDro[i];
            posMax=i;
        }
        minDepuisDro.push_back({minCour,posMin});
        maxDepuisDro.push_back({maxCour,posMax});
    }
    reverse(minDepuisDro.begin(),minDepuisDro.end());
    reverse(maxDepuisDro.begin(),maxDepuisDro.end());

    //cout<<"deb OK"<<endl;
    int valMinGau=minJusquaGau.back().first,valMaxGau=maxJusquaGau.back().first,posMaxGau=maxJusquaGau.back().second;
    int valMinDro=minJusquaDro.back().first,valMaxDro=maxJusquaDro.back().first,posMaxDro=maxJusquaDro.back().second;
    //cout<<"!"<<posMaxGau<<" "<<posMaxDro<<endl;
    if (valMinGau+valMaxDro<0 or valMinDro+valMaxGau<0) {
        return false;
    }
    int posGau=posMaxGau-1,posDro=posMaxDro-1;
    while (posGau>=0 and posDro>=0) {
        if (maxJusquaGau[posGau].first+minJusquaDro[posDro].first>=0) {
            posGau=maxJusquaGau[posGau].second-1;
        }
        else if (maxJusquaDro[posDro].first+minJusquaGau[posGau].first>=0) {
            posDro=maxJusquaDro[posDro].second-1;
        }
        else {
            return false;
        }
    } 
    //cout<<"mid OK"<<endl;
    /*for (auto i:maxDepuisGau) {
        cout<<i.first<<" "<<i.second<<"\t";
    } 
    cout<<endl;
    for (auto i:maxDepuisDro) {
        cout<<i.first<<" "<<i.second<<"\t";
    }
    cout<<endl;*/

    posGau=posMaxGau+1;
    posDro=posMaxDro+1;
    while (posGau<tailleGau and posDro<tailleDro) {
        //cout<<posGau<<" "<<posDro<<endl;
        if (maxDepuisGau[posGau].first+minDepuisDro[posDro].first>=0) {
            posGau=maxDepuisGau[posGau].second+1;
        }
        else if (maxDepuisDro[posDro].first+minDepuisGau[posGau].first>=0) {
            posDro=maxDepuisDro[posDro].second+1;
        }
        else {
            return false;
        }
    } 
    //cout<<"fin OK"<<endl;
    return true;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbVal>>posInit>>tempsInit;
    for (int i=1;i<=nbVal;i++) {
        cin>>val[i];
    }
    verif(23437500);
    int deb=0,fin=INFINI,mid;
    while (deb!=fin) {
        mid=(deb+fin)/2;
        if (verif(mid)) {
            fin=mid;
        }
        else {
            deb=mid+1;
        }
    }
    cout<<(deb+tempsInit-1)/tempsInit<<endl;
    return 0;
}
 

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50