Submission #493704

#TimeUsernameProblemLanguageResultExecution timeMemory
493704vulpesCountries (BOI06_countries)C++17
100 / 100
4 ms340 KiB
#include <bits/stdc++.h> using namespace std; struct country { int x, y, s, ind; bool operator<(country a) { return s > a.s; } } a[1007]; int dist(int i, int j) { return (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i].x >> a[i].y >> a[i].s; a[i].ind = i; } sort(a, a + n); vector<int> r(n); for (int i = 0; i < n; i++) { vector<int> v; for (int j = 0; j < i; j++) { if (a[j].s > a[i].s * dist(i, j)) { v.push_back(j); } } if (v.empty()) { r[a[i].ind] = 0; continue; } int h = v[0], c = 1; for (int j = 1; j < v.size(); j++) { int d1 = a[h].s * dist(v[j], i); int d2 = a[v[j]].s * dist(h, i); if (d1 == d2) { c++; continue; } if (d1 < d2) { h = v[j]; c = 1; } } if (c > 1) { r[a[i].ind] = -1; continue; } r[a[i].ind] = (r[a[h].ind] ? r[a[h].ind] : a[h].ind + 1); } for (int i = 0; i < n; i++) { if (r[i] > 0) { cout << r[i] << endl; continue; } cout << (r[i] ? "D" : "K") << endl; } }

Compilation message (stderr)

countries.cpp: In function 'int main()':
countries.cpp:37:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int j = 1; j < v.size(); j++) {
      |                         ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...