oj.uz

Submission #1003479

# Submission time Handle Problem Language Result Execution time Memory
1003479 2024-06-20T11:41:18 Z vjudge1 Tiles (BOI24_tiles) C++17
0 / 100
 29 ms 5856 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]%2) {
      ans = min(ans, x[i]-1);
    }
    else if (y[i]%2) {
      ans = min(ans, x[i]);
    }
  }
  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:115:1: warning: "/*" within comment [-Wcomment]
  115 | /*
      |

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 0 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 344 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 0 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 0 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 344 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 0 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 0 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 12 ms 2976 KB Output is correct
3 Correct 15 ms 3036 KB Output is correct
4 Correct 16 ms 3420 KB Output is correct
5 Correct 16 ms 3420 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 26 ms 5596 KB Output is correct
9 Correct 25 ms 5680 KB Output is correct
10 Correct 25 ms 5468 KB Output is correct
11 Correct 25 ms 5712 KB Output is correct
12 Correct 23 ms 5488 KB Output is correct
13 Correct 25 ms 5856 KB Output is correct
14 Incorrect 29 ms 5720 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 5716 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 0 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 0 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 344 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -