[C++] BOJ (백준) 7568 : 덩치

문제

7568번: 덩치 (acmicpc.net)

7568번: 덩치

코드

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int, int>> v;

void input() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  v = vector<pair<int, int>>(n);
  for (auto &i: v) {
    int x, y;
    cin >> x >> y;
    i = {x, y};
  }
}

void solve() {
  for (auto i: v) {
    int rank = 1;
    for (auto j: v) {
      if (i.first < j.first && i.second < j.second) rank++;
    }
    cout << rank << ' ';
  }
}

int main() {
  input();
  solve();
  return 0;
}

 

설명

이중 for문으로 벡터 각각의 요소에 대해 rank를 매긴다.
이러면 O(n^2)이 되는데, O(n log n)으로도 풀려고 시도해봤지만 실패했다...