oj.uz

Submission #1003483

# Submission time Handle Problem Language Result Execution time Memory
1003483 2024-06-20T11:43:27 Z vjudge1 Tiles (BOI24_tiles) C++17
0 / 100
 36 ms 5592 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;

int n, m, x[N], y[N];

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }

  int ans = m;
  for (int i = 0; i < n; i++) {
    if (x[i]&1) {
      ans = min(ans, x[i]-1);
    }
    if (y[i]&1) {
      ans = min(ans, x[i]);
    }
  }
  assert(ans%2 == 0);
  cout << ans << "\n";
}

/*
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()

const int N = 2e5+5, inf = INT_MAX;

int n, m, x[N], y[N];
pair<int, int> s;
vector<pair<int, int>> odd, even;
set<pair<int, int>>  odd2, even2;

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m; 
  if (m&1) m--;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i]; 
    if (x[i]&1) m = min(m, x[i]-1);
  }

  for (int i = 0; i < n; i++) {
    x[i] = min(x[i], m);
  }

  for (int i = 0; i < n; i++) {
    if (y[i] != y[(i+1)%n]) continue;

    if (y[i]&1) odd.push_back(make_pair(min(x[i], x[(i+1)%n]), -max(x[i], x[(i+1)%n])));
    else even.push_back(make_pair(min(x[i], x[(i+1)%n]), -max(x[i], x[(i+1)%n])));
  }
  sort(all(odd));
  sort(all(even));

  int R = -1;
  for (int i = 0; i < odd.size(); i++) {
    odd[i].second = -odd[i].second;

    if (odd[i].second > R) {
      odd2.insert(odd[i]);
      R = odd[i].second;
    }
  }
  
  R = -1;
  for (int i = 0; i < even.size(); i++) {
    even[i].second = -even[i].second;

    if (even[i].second > R) {
      even2.insert(even[i]);
      R = even[i].second;
    }
  }

  for (int i = 0; i < n; i++) {
    s[i] = make_pair(y[i], i);
  }
  sort(s, s+n);

  int ans = m;
  for (int ii = 0; ii < n; ii++) {
    int i = s[i].second;
    
    if (y[i]&1) {
      // miro los even
      auto it = even2.upper_bound(make_pair(x[i]+1, x[i]+1));
      if (it == even2.begin()) continue;

      it = prev(it);
      if (it->second >= x[i]) ans = min(ans, x[i]);
    }
    else {
      // miro los odds
      auto it = upper_bound(all(odd2), make_pair(x[i]+1, x[i]+1));
      if (it == odd2.begin()) continue;

      it = prev(it);
      if (it->second >= x[i]) ans = min(ans, x[i]);
    }
  }
  if (ans&1) ans--;

  cout << ans << "\n";
}

/*
  cin >> n >> m;
  for (int i = 0; i <= m; i++) {
    mx[i] = -inf;
    mn[i] = inf;
  }

  bool ok = 1;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];

    if (x[i]%2) m = x[i]-1;

    mx[x[i]] = max(mx[x[i]], y[i]);
    mn[x[i]] = min(mn[x[i]], y[i]);
  
    if (0 < i < n-1 && (x[i] < x[i-1] || y[i] > y[i-1])) ok = 0;
  }
  if (max(x[n-1], y[n-1])) ok = 0;

  if (ok) {
    int ans = m;
    for (int i = 0; i < n; i++) {
      if (y[i]%2) {
        ans = x[i];
        break;
      }
      else if (i && (x[i]-x[i-1])%2) {
        ans = x[i]-1;
        break;
      }
    }
    cout << ans << "\n";
    return 0;
  }

  int ans = 0;
  for (int i = 0; i <= m; i+=2) {
    bool ok = 1;
    for (int j = 0; j <= 1000; j++) {
      // si en x = ans+1 hay un punto > j y otro <= j no se puede
      // si en
      if (mx[ans+1] > j && mn[ans+1] <= j) {
        ok = 0;
        break;
      }
    }
    if (!ok) break;

    ans += 2;
  }
  cout << ans << "\n";
  */

Compilation message

Main.cpp:116:1: warning: "/*" within comment [-Wcomment]
  116 | /*
      |

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 13 ms 2988 KB Output is correct
3 Correct 17 ms 3160 KB Output is correct
4 Correct 16 ms 3540 KB Output is correct
5 Correct 21 ms 3416 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 25 ms 5380 KB Output is correct
9 Correct 30 ms 5536 KB Output is correct
10 Correct 36 ms 5564 KB Output is correct
11 Correct 28 ms 5536 KB Output is correct
12 Correct 33 ms 5592 KB Output is correct
13 Correct 27 ms 5200 KB Output is correct
14 Incorrect 27 ms 5128 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 4780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -