Submission #1031012

#TimeUsernameProblemLanguageResultExecution timeMemory
1031012tolbiRail (IOI14_rail)C++17
22 / 100
85 ms98640 KiB
#include "rail.h" #include <bits/stdc++.h> using namespace std; map<pair<int,int>,int> mp; int _dist[5001][5001]; int dist(int a, int b){ if (_dist[a][b]==-1) _dist[a][b]=getDistance(a,b); return _dist[a][b]; } void findLocation(int N, int first, int location[], int stype[]) { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j){ _dist[i][j]=-1; if (i==j) _dist[i][j]=0; } } int c = 0, d = 1; for (int i = 2; i < N; i++){ if (dist(c,i)<dist(c,d)) d=i; } vector<int> left; vector<int> right; stype[c]=1,stype[d]=2; location[c]=first,location[d]=first+dist(c,d); for (int i = 0; i < N; i++){ if (i==c || i==d) continue; if (dist(c,i)==dist(c,d)+dist(d,i)){ if (dist(d,i)<dist(c,d)){ location[i]=location[d]-dist(d,i); stype[i]=1; } else left.push_back(i); } else { right.push_back(i); } } sort(left.begin(), left.end(), [&](int a, int b){ return dist(d,a)<dist(d,b); }); sort(right.begin(), right.end(), [&](int a, int b){ return dist(c,a)<dist(c,b); }); if (left.size()){ set<int> virt; virt.insert(left[0]); int fiC = left[0]; location[fiC]=location[d]-dist(d,fiC); stype[fiC]=1; for (int _ = 1; _ < left.size(); _++){ int v = left[_]; int vloc = location[fiC]+dist(fiC,v); int hh = dist(d,v)-(location[d]-vloc); if (hh%2 || virt.find(vloc-hh/2)==virt.end()){ stype[v]=1; location[v]=location[d]-dist(d,v); fiC = v; virt.insert(fiC); } else { stype[v]=2; location[v]=vloc; } } } if (right.size()){ set<int> virt; virt.insert(right[0]); int fiD = right[0]; location[fiD]=location[c]+dist(c,fiD); stype[fiD]=2; for (int _ = 1; _ < right.size(); _++){ int v = right[_]; int vloc = location[fiD]-dist(fiD,v); int hh = dist(c,v)-(vloc-location[c]); if (hh%2 || virt.find(vloc+hh/2)==virt.end()){ stype[v]=2; location[v]=location[c]+dist(c,v); fiD = v; virt.insert(fiD); } else { stype[v]=1; location[v]=vloc; } } } }

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int _ = 1; _ < left.size(); _++){
      |                   ~~^~~~~~~~~~~~~
rail.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for (int _ = 1; _ < right.size(); _++){
      |                   ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...