Submission #1051776

#TimeUsernameProblemLanguageResultExecution timeMemory
1051776MarwenElarbiFountain Parks (IOI21_parks)C++17
5 / 100
119 ms32092 KiB
#include <bits/stdc++.h> using namespace std; #include "parks.h" #define pb push_back #define fi first #define se second const int nax=2e5+5; int pre[nax]; int dis(pair<int,int> a,pair<int,int> b){ return abs(a.fi-b.fi)+abs(a.se-b.se); } int construct_roads(std::vector<int> x, std::vector<int> y) { if (x.size() == 1) { build({}, {}, {}, {}); return 1; } std::vector<int> u, v, a, b; int n=y.size(); vector<pair<pair<int,int>,int>> cor; vector<pair<int,int>> tab[nax]; for (int i = 0; i < n; ++i) tab[y[i]].pb({x[i],i}); for (int i = 0; i < n; ++i) cor.pb({{y[i],x[i]},i}); for (int i = 2; i < nax; ++i) pre[i]=pre[i-1]+tab[i].size(); sort(cor.begin(),cor.end()); bool test=true; for (int i = 0; i < n; ++i) { if(pre[y[i]-1]>0&&tab[y[i]-2].size()==0) test=false; if(pre[y[i]-1]>0&&tab[y[i]].size()==1&&tab[y[i]-2].size()==1){ if(abs(tab[y[i]][0].fi-tab[y[i]-2][0].fi>0)) test=false; } } if(!test) return 0; for (int i = 0; i < n-1; ++i) { if(i<n-2){ if(dis(cor[i].fi,cor[i+2].fi)==2){ if(cor[i].fi.se==2) a.pb(1); else a.pb(5); b.pb(cor[i].fi.fi+1); u.pb(cor[i].se); v.pb(cor[i+2].se); } } if(dis(cor[i].fi,cor[i+1].fi)!=2) continue; if(cor[i].fi.se!=cor[i+1].fi.se){ a.pb(3); b.pb(cor[i].fi.fi-1); u.pb(cor[i].se); v.pb(cor[i+1].se); }else{ if(cor[i].fi.se==2) a.pb(1); else a.pb(5); b.pb(cor[i].fi.fi+1); u.pb(cor[i].se); v.pb(cor[i+1].se); } } build(u, v, a, b); return 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...
#Verdict Execution timeMemoryGrader output
Fetching results...