Submission #1001558

#TimeUsernameProblemLanguageResultExecution timeMemory
1001558SharkyRail (IOI14_rail)C++17
30 / 100
87 ms98672 KiB
// amogus orz #include "rail.h" #include <bits/stdc++.h> using namespace std; const int inf = 1e9; const int N = 5001; int cache[N][N]; int dist(int i, int j) { if (i == j) return 0; if (cache[i][j] != -1) return cache[i][j]; return cache[i][j] = cache[j][i] = getDistance(i, j); } void findLocation(int n, int first, int pos[], int stype[]) { map<int, char> sus; vector<char> t(n, '?'); t[0] = 'C'; pos[0] = first; sus[first] = 'C'; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cache[i][j] = -1; int mn = inf, id = 0; for (int i = 1; i < n; i++) if (dist(0, i) < mn) mn = dist(0, i), id = i; t[id] = 'D'; pos[id] = first + dist(0, id); sus[pos[id]] = 'D'; vector<pair<int, int>> l, r; for (int i = 1; i < n; i++) { if (i == id) continue; if (dist(0, id) + dist(id, i) == dist(0, i) && dist(0, i) > dist(id, i)) { t[i] = 'C'; pos[i] = first + dist(0, id) - dist(id, i); sus[pos[i]] = 'C'; continue; } if (dist(0, i) > dist(id, i)) l.push_back({dist(id, i), i}); else r.push_back({dist(0, i), i}); } sort(l.begin(), l.end()); sort(r.begin(), r.end()); int leftmost = 0, rightmost = id; for (int i = 0; i < l.size(); i++) { int cur = l[i].second; int magic = pos[leftmost] + (dist(cur, leftmost) + dist(leftmost, id) - dist(id, cur)) / 2; if (sus[magic] == 'C') { t[cur] = 'D'; pos[cur] = dist(cur, leftmost) + pos[leftmost]; sus[pos[cur]] = 'D'; } else { t[cur] = 'C'; pos[cur] = pos[id] - dist(id, cur); sus[pos[cur]] = 'C'; leftmost = cur; } } for (int i = 0; i < r.size(); i++) { int cur = r[i].second; int magic = pos[rightmost] - (dist(cur, rightmost) + dist(rightmost, 0) - dist(cur, 0)) / 2; if (sus[magic] == 'C') { t[cur] = 'D'; pos[cur] = pos[0] + dist(0, cur); sus[pos[cur]] = 'D'; rightmost = cur; } else { t[cur] = 'C'; pos[cur] = pos[rightmost] - dist(rightmost, cur); sus[pos[cur]] = 'C'; } } for (int i = 0; i < n; i++) { stype[i] = (t[i] == 'C' ? 1 : 2); // cout << stype[i] << ' ' << pos[i] << '\n'; } }

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < l.size(); i++) {
      |                     ~~^~~~~~~~~~
rail.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...