Submission #610779

#TimeUsernameProblemLanguageResultExecution timeMemory
610779nohaxjustsofloJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
177 ms110196 KiB
#include <bits/stdc++.h> #include <iostream> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set; mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count()); //uniform_int_distribution<int> gen; ///(min, max) //int random() {return gen(mt_rand);} const int mxN=30001; const int mod=998244353; const int mxlogN=40; const int mxK=26; const int inf=1e9; const int K=600; int vis[6000000]; bool done[6000000]; int a[mxN], b[mxN],n,m; vector<int> have, who2[mxN]; vector<pair<int,int>> who[mxN]; int pos(int x) { return lower_bound(have.begin(),have.end(),x)-have.begin(); } struct st { int x,p,i; }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i=0; i<m; i++) cin >> a[i] >> b[i]; for(int i=0; i<m; i++) { who[a[i]].push_back({a[i],b[i]}); who2[b[i]].push_back(a[i]%b[i]); } for(int i=1; i<mxN; i++) { sort(who2[i].begin(),who2[i].end()); who2[i].erase(unique(who2[i].begin(),who2[i].end()),who2[i].end()); for(int k=0; k*i<n; k++) for(int j:who2[i]) if(j+k*i<n) have.push_back(i*n+j+k*i); } for(int i=0; i<n; i++) for(auto& par:who[i]) par.first=pos(par.second*n+par.first); deque<st> q; q.push_back({a[0],b[0],pos(b[0]*n+a[0])}); int sz=have.size(); for(int i=0; i<sz; i++) vis[i]=inf; vis[pos(b[0]*n+a[0])]=0; while(q.size()) { auto cur=q.front(); q.pop_front(); int x=cur.x,p=cur.p,i=cur.i; if(x==a[1]) { cout << vis[i] << "\n"; return 0; } if(done[i]) continue; done[i]=1; while(who[x].size()) { auto cur2=who[x].back(); who[x].pop_back(); int nw=cur2.first; if(vis[i]<vis[nw]) { vis[nw]=vis[i]; q.push_front({x,cur2.second,nw}); } } if(x-p>=0) { int nw=i-who2[p].size(); if(vis[i]+1<vis[nw]) { vis[nw]=vis[i]+1; q.push_back({x-p,p,nw}); } } if(x+p<n) { int nw=i+who2[p].size(); if(vis[i]+1<vis[nw]) { vis[nw]=vis[i]+1; q.push_back({x+p,p,nw}); } } } cout << "-1" << "\n"; return 0; } /* 5 3 0 2 1 1 4 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...