Advertisement
erek1e

IOI '04 P1 - Artemis

Jul 23rd, 2022
985
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.25 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. void compress(vector<int> &v) {
  8.     vector<int> v2 = v;
  9.     sort(v2.begin(), v2.end());
  10.     // do not need to remove duplicates since there are no duplicates
  11.     for (int &x : v) x = 1+lower_bound(v2.begin(), v2.end(), x)-v2.begin();
  12. }
  13.  
  14. struct Point {
  15.     int x, y, id;
  16.     bool operator < (const Point &p2) const {
  17.         return pair<int, int>(x, y) < pair<int, int>(p2.x, p2.y);;
  18.     }
  19. };
  20.  
  21. int main() {
  22.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  23.     int n, t; cin >> n >> t;
  24.     vector<int> x(n), y(n);
  25.     for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];
  26.     compress(x);
  27.     compress(y);
  28.  
  29.     vector<Point> points(n);
  30.     for (int i = 0; i < n; ++i) points[i].x = x[i], points[i].y = y[i], points[i].id = i+1;
  31.     sort(points.begin(), points.end());
  32.  
  33.     vector<int> treesDL(n); // trees down and left (excluding itself)
  34.     for (int i = 0; i < n; ++i) {
  35.         for (int j = 0; j < n; ++j) {
  36.             if (points[j].x < points[i].x && points[j].y < points[i].y) ++treesDL[i];
  37.         }
  38.     }
  39.  
  40.     int minTrees = n+1, bestI = 0, bestJ = 0;
  41.     for (int i = 0; i < n && minTrees > t; ++i) { // fix one end tree
  42.         int treesBelow = 0;
  43.         vector<int> treesLeft(1+n); // number of trees at each y-value
  44.         for (int j = 0; j < i; ++j) {
  45.             if (points[j].y < points[i].y) ++treesBelow;
  46.             ++treesLeft[points[j].y];
  47.         }
  48.         // convert treesLeft into prefix sums
  49.         for (int yy = 1; yy <= n; ++yy) treesLeft[yy] += treesLeft[yy-1];
  50.  
  51.         for (int j = i+1; j < n; ++j) {
  52.             // find number of trees enclosed by trees i and j
  53.             int trees;
  54.             if (points[j].y > points[i].y) {
  55.                 trees = treesDL[i] + treesDL[j] - treesBelow - treesLeft[points[j].y] + 1; // add tree i
  56.             } else {
  57.                 trees = treesBelow + treesLeft[points[j].y] - treesDL[i] - treesDL[j] + 2; // add trees i and j
  58.             }
  59.             if (trees >= t && trees < minTrees) minTrees = trees, bestI = points[i].id, bestJ = points[j].id;
  60.  
  61.             if (points[j].y < points[i].y) ++treesBelow;
  62.         }
  63.     }
  64.     cout << bestI << ' ' << bestJ << endl;
  65.     return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement