Submission #1184620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184620		inesfi	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	310 ms	86640 KiB

skyscraper

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

#define endl "\n"
//#define int long long

const int TAILLEMAXI=30*1000+2,PMAXI=175;
int dejavu[TAILLEMAXI][PMAXI]; ///endroit,P
vector<int> depart[TAILLEMAXI];
int nbvilles,nbjumpers;
vector<pair<int,int>> encours[PMAXI]; ///////// [nbcoups], pos, P

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>nbvilles>>nbjumpers;
    int posfinal;
    for (int i=0;i<nbjumpers;i++){
        int a,b;
        cin>>a>>b;
        depart[a].push_back(b);
        if (i==0){
            encours[0].push_back({a,0});
        }
        else if (i==1){
            posfinal=a;
        }
    }
    int rep=0,nbelem=1;
    while (nbelem!=0){
        for (int icase=0;icase<PMAXI;icase++){
            while ((int)encours[icase].size()!=0){
                int pos=encours[icase].back().first,P=encours[icase].back().second;
                encours[icase].pop_back();
                nbelem--;
                if (pos>=0 and pos<nbvilles and dejavu[pos][P]==0){
                    dejavu[pos][P]=1;
                    if (pos==posfinal){
                        cout<<PMAXI*rep+icase<<endl;
                        return 0;
                    }
                    if (P!=0){
                        encours[icase].push_back({pos,0});
                        encours[(icase+1)%PMAXI].push_back({pos-P,P});
                        encours[(icase+1)%PMAXI].push_back({pos+P,P});
                        nbelem+=3;
                    }
                    else {
                        for (int i:depart[pos]){
                            if (i<PMAXI){
                                encours[icase].push_back({pos,i});
                                nbelem++;
                            }
                            else {
                                int a=1;
                                while (pos-a*i>=0){
                                    encours[(icase+a)%PMAXI].push_back({pos-a*i,0});
                                    nbelem++;
                                    a++;
                                }
                                a=1;
                                while (pos+a*i<nbvilles){
                                    encours[(icase+a)%PMAXI].push_back({pos+a*i,0});
                                    nbelem++;
                                    a++;
                                }
                            }
                        }
                    }
                }
            }
        }
        rep++;
    }
    cout<<-1<<endl;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43