fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct DataPoint {
  5.     vector<double> coordinates;
  6.     int index;
  7.     double distance;
  8. };
  9.  
  10. struct Compare {
  11.     bool operator()(const pair<double, int>& a, const pair<double, int>& b) {
  12.         if (a.first == b.first) {
  13.             return a.second > b.second; 
  14.         }
  15.         return a.first < b.first; 
  16.     }
  17. };
  18.  
  19. double manhattanDistance(const vector<double>& a, const vector<double>& b) {
  20.     double dist = 0;
  21.     for (size_t i = 0; i < a.size(); ++i) {
  22.         dist += abs(a[i] - b[i]);
  23.     }
  24.     return dist;
  25. }
  26.  
  27. void updateDistance(DataPoint& point, const vector<double>& reference) {
  28.     point.distance = manhattanDistance(point.coordinates, reference);
  29. }
  30.  
  31. int main() {
  32.     int n, m, k, q;
  33.     cin >> n >> m >> k >> q;
  34.  
  35.     vector<DataPoint> points(n);
  36.     for (int i = 0; i < n; ++i) {
  37.         points[i].index = i + 1; 
  38.         points[i].coordinates.resize(m);
  39.         for (int j = 0; j < m; ++j) {
  40.             cin >> points[i].coordinates[j];
  41.         }
  42.     }
  43.  
  44.     vector<double> reference(m);
  45.     for (int i = 0; i < m; ++i) {
  46.         cin >> reference[i];
  47.     }
  48.  
  49.     vector<vector<double>> queries(q, vector<double>(m + 1));
  50.     for (int i = 0; i < q; ++i) {
  51.         cin >> queries[i][0];
  52.         for (int j = 1; j <= m; ++j) {
  53.             cin >> queries[i][j];
  54.         }
  55.     }
  56.  
  57.     for (auto& point : points) {
  58.         updateDistance(point, reference);
  59.     }
  60.  
  61.     for (const auto& query : queries) {
  62.         int idx = static_cast<int>(query[0]) - 1;
  63.         for (int j = 0; j < m; ++j) {
  64.             points[idx].coordinates[j] = query[j + 1];
  65.         }
  66.  
  67.         updateDistance(points[idx], reference);
  68.  
  69.         priority_queue<pair<double, int>, vector<pair<double, int>>, Compare> pq;
  70.         for (const auto& point : points) {
  71.             pq.push({point.distance, point.index});
  72.             if (pq.size() > k) pq.pop();
  73.         }
  74.  
  75.         vector<int> knn;
  76.         while (!pq.empty()) {
  77.             knn.push_back(pq.top().second);
  78.             pq.pop();
  79.         }
  80.         sort(knn.begin(), knn.end());
  81.  
  82.         for (size_t i = 0; i < knn.size(); ++i) {
  83.             if (i > 0) cout << " ";
  84.             cout << knn[i];
  85.         }
  86.         cout << "\n";
  87.     }
  88.  
  89.     return 0;
  90. }
  91.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin 
5 2 2 3
1.0 1.0
2.0 2.0
3.0 3.0
4.0 4.0
5.0 5.0
3.0 3.0
3 3.0 5.0
2 2.5 4.0
4 1.0 1.0
stdout 
3 4
2 4
2 3
https://ideone.com/4bhy3o
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!