oj.uz

Submission #640206

# Submission time Handle Problem Language Result Execution time Memory
640206 2022-09-14T01:36:35 Z iee Matching (COCI20_matching) C++17
11 / 110
 365 ms 9748 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, x[N], y[N], vis[N];
vector<int> gx[N], gy[N];
int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> x[i] >> y[i];
    gx[x[i]].push_back(i);
    gy[y[i]].push_back(i);
  }
  for (int S = 0; S < (1 << n); ++S) {
    vector<pair<int, int>> ex, ey;
    fill_n(vis, n, 0);
    for (int i = 0; i < n; ++i) if (S >> i & 1) {
      if (gx[x[i]].size() == 1 || gx[x[i]][1] == i || vis[gx[x[i]][1]]) continue;
      ex.emplace_back(i, gx[x[i]][1]), vis[i] = vis[gx[x[i]][1]] = 1;
    } else {
      if (gy[y[i]].size() == 1 || gy[y[i]][1] == i || vis[gy[y[i]][1]]) continue;
      ey.emplace_back(i, gy[y[i]][1]), vis[i] = vis[gy[y[i]][1]] = 1;
    }
    if (count(vis, vis + n, 0)) continue;
    for (auto EX: ex) {
      int xx = x[EX.first], ly = min(y[EX.first], y[EX.second]), ry = max(y[EX.first], y[EX.second]);
      for (auto EY: ey) {
        int yy = y[EY.first], ux = min(x[EY.first], x[EY.second]), dx = max(x[EY.first], x[EY.second]);
        if (xx >= ux && xx <= dx && yy >= ly && yy <= ry) {
          goto fail;
        }
      }
    }
    puts("DA");
    for (auto it: ex) cout << it.first + 1 << ' ' << it.second + 1 << '\n';
    for (auto it: ey) cout << it.first + 1 << ' ' << it.second + 1 << '\n';
    return 0;
    fail:;
  }
  puts("NE");
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9704 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9680 KB Output is correct
6 Correct 354 ms 9704 KB Output is correct
7 Correct 365 ms 9748 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9704 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9680 KB Output is correct
6 Correct 354 ms 9704 KB Output is correct
7 Correct 365 ms 9748 KB Output is correct
8 Incorrect 5 ms 9684 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9704 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9680 KB Output is correct
6 Correct 354 ms 9704 KB Output is correct
7 Correct 365 ms 9748 KB Output is correct
8 Incorrect 5 ms 9684 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9704 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9680 KB Output is correct
6 Correct 354 ms 9704 KB Output is correct
7 Correct 365 ms 9748 KB Output is correct
8 Incorrect 5 ms 9684 KB Output isn't correct
9 Halted 0 ms 0 KB -