Submission #853652

#TimeUsernameProblemLanguageResultExecution timeMemory
853652idiotcomputerWalk (CEOI06_walk)C++11
100 / 100
90 ms12248 KiB
#include <bits/stdc++.h> using namespace std; struct point { int x,y,idx,pos; }; struct rect { int x1,y1,x2,y2; int n1 = -1; int n2 = -1; long long int s1 = (long long int) 1e15; long long int s2 = (long long int) 1e15; int b1 = -1; int b2 = -1; }; bool comp(point &a, point &b){ if (a.x == b.x){ if (a.y == b.y){ return a.pos < b.pos; } return a.y > b.y; } return a.x < b.x; } int dist(int x1, int y1, int x2, int y2){ return abs(x1-x2) + abs(y1-y2); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int x,y; cin >> x >> y; int n; cin >> n; vector<point> points; vector<rect> rects; rect temp; point t2; int cnt = 0; for (int i =0; i < n; i++){ cin >> temp.x1 >> temp.y1 >> temp.x2 >> temp.y2; if (temp.x1 >= x){ continue; } temp.x2 = min(temp.x2,x-1); rects.push_back(temp); points.push_back(t2); points.push_back(t2); // cnt++; points[2*cnt].x = temp.x1-1; points[2*cnt].y = temp.y1-1; points[2*cnt].idx = cnt; points[2*cnt].pos = 0; points[2*cnt+1].x = temp.x2+1; points[2*cnt+1].y = temp.y2+1; points[2*cnt+1].idx = cnt; points[2*cnt+1].pos = 1; cnt++; } temp.x1 = x; temp.x2 = x; temp.y1 = y; temp.y2 = y; rects.push_back(temp); points.push_back(t2); points.push_back(t2); n = (int) rects.size(); points[2*n-2].x = temp.x1; points[2*n-2].y = temp.y1; points[2*n-2].idx = (int) (rects.size())-1; points[2*n-2].pos = 0; points[2*n-1].x = temp.x2; points[2*n-1].y = temp.y2; points[2*n-1].idx = (int) (rects.size())-1; points[2*n-1].pos = 1; sort(points.begin(),points.end(),comp); set<pair<int,int>> all; //cout << "\n\n"; for (int i =2*n-1; i >= 0; i--){ // cout << points[i].x << "," << points[i].y << " " << points[i].idx << " " << points[i].pos << '\n'; if (points[i].pos == 1){ auto it = all.lower_bound({rects[points[i].idx].y1,-1}); while (it != all.end() && (*it).first <= (points[i].y)-1){ if (points[(*it).second].pos == 0){ rects[points[(*it).second].idx].n1 = points[i].idx; } else { rects[points[(*it).second].idx].n2 = points[i].idx; } auto it2 = it; it++; all.erase(it2); } } all.insert({points[i].y,i}); } /* for (int i =0; i < n; i++){ cout << i << ": " << rects[i].x1 << "," << rects[i].y1 << " " << rects[i].x2 << "," << rects[i].y2 <<'\n'; cout << rects[i].n1 << " - " << rects[i].n2 << "\n\n"; }*/ int next; int cidx; int v1,v2; for (int i =0; i < 2*n; i++){ cidx = points[i].idx; if (points[i].pos == 0){ next = rects[cidx].n1; } else { next = rects[cidx].n2; } if (next == -1){ if (points[i].pos == 0){ rects[cidx].s1 = dist(0,0,points[i].x,points[i].y); } else { rects[cidx].s2 = dist(0,0,points[i].x,points[i].y); } continue; } if (points[i].pos == 0){ v1 = rects[next].s1+dist(points[i].x,points[i].y,rects[next].x1-1,rects[next].y1-1); v2 = rects[next].s2+dist(points[i].x,points[i].y,rects[next].x2+1,rects[next].y2+1); rects[cidx].s1 = min(v1,v2); if (v1 < v2){ rects[cidx].b1 = 0; } else { rects[cidx].b1 = 1; } } else { v1 = rects[next].s1+dist(points[i].x,points[i].y,rects[next].x1-1,rects[next].y1-1); v2 = rects[next].s2+dist(points[i].x,points[i].y,rects[next].x2+1,rects[next].y2+1); rects[cidx].s2 = min(v1,v2); if (v1 < v2){ rects[cidx].b2 = 0; } else { rects[cidx].b2 = 1; } } } pair<int,int> rt; vector<pair<int,int>> res; int curr = n-1; int cp = 0; int cx,cy,ty,tx; int wp; rects[n-1].x1 += 1; rects[n-1].y1 += 1; // cout << "\n\n"; while (true){ // cout << curr << "," << cp << '\n'; if (cp == 0){ cx = rects[curr].x1-1; cy = rects[curr].y1-1; next = rects[curr].n1; wp = rects[curr].b1; } else { cx = rects[curr].x2+1; cy = rects[curr].y2+1; next = rects[curr].n2; wp = rects[curr].b2; } // cout << cx << "," << cy << " " << next << " " << wp << "\n\n"; if (next == -1){ tx = 0; ty = 0; } else { tx = rects[next].x2+1; if (wp == 0){ ty = rects[next].y1-1; } else { ty = rects[next].y2+1; } } rt.first = tx - cx; rt.second = 0; res.push_back(rt); rt.first = 0; rt.second = ty - cy; res.push_back(rt); if (wp == 0){ rt.first = rects[next].x1-1 - tx; rt.second = 0; res.push_back(rt); } if (next == -1){ break; } curr = next; cp = wp; } /* cout << "\n\n"; for (int i =0; i < n; i++){ cout << i << ": " << rects[i].x1 << "," << rects[i].y1 << " " << rects[i].x2 << "," << rects[i].y2 <<'\n'; cout << rects[i].n1 << " - " << rects[i].n2 << "\n"; cout << rects[i].b1 << ',' << rects[i].s1 << " - " << rects[i].b2 << "," << rects[i].s2 << "\n\n"; }*/ wp = -1; cx = 0; cy = 0; vector<pair<int,int>> fin; for (int i =res.size()-1; i >= 0; i--){ if (res[i].first == 0){ if (wp == 1 || wp ==-1){ cy -= res[i].second; wp = 1; } else{ fin.push_back({cx,cy}); cx = 0; cy = -1 * res[i].second; wp = 1; } } else { if (wp == 0 || wp ==-1){ cx -= res[i].first; wp = 0; } else{ fin.push_back({cx,cy}); cx = -1 * res[i].first; cy = 0; wp = 0; } } } if (wp != -1){ fin.push_back({cx,cy}); } cout << rects[n-1].s1 << "\n"; cout << fin.size() << '\n'; for (int i =0; i < fin.size(); i++){ cout << fin[i].first << " " << fin[i].second << '\n'; } return 0; }

Compilation message (stderr)

walk.cpp: In function 'int main()':
walk.cpp:242:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  242 |     for (int i =0; i < fin.size(); i++){
      |                    ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...