oj.uz

Submission #1022039

# Submission time Handle Problem Language Result Execution time Memory
1022039 2024-07-13T09:18:37 Z huutuan Tiles (BOI24_tiles) C++14
15 / 100
 35 ms 9432 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
	friend ostream& operator<<(ostream& os, P p) {
		return os << "(" << p.x << "," << p.y << ")"; }
};

template<class P>
vector<P> convexHull(vector<P> pts) {
	if (sz(pts) <= 1) return pts;
	sort(all(pts));
	vector<P> h(sz(pts)+1);
	int s = 0, t = 0;
	for (int it = 2; it--; s = --t, reverse(all(pts)))
		for (P p : pts) {
			while (t >= s + 2 && h[t-2].cross(h[t-1], p) <= 0) t--;
			h[t++] = p;
		}
	return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])};
}

using pt=Point<int>;

const int N=2e5+10;
int n, m;
pt a[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   for (int i=1; i<=n; ++i) cin >> a[i].x >> a[i].y;
   if (n==4 || n==6){
      vector<pt> v;
      for (int i=1; i<=n; ++i){
         while (sz(v)>=2 && v[sz(v)-2].cross(v[sz(v)-1], a[i])==0) v.pop_back();
         v.push_back(a[i]);
      }
      auto v2=v;
      for (auto &i:v){
         while (sz(v2)>=2 && v2[sz(v2)-2].cross(v2[sz(v2)-1], i)==0) v2.pop_back();
         v2.push_back(i);
      }
      n=sz(v2)/2;
      for (int i=1; i<=n; ++i) a[i]=v2[i-1];
      if (n==4){
         set<int> st;
         for (int i=1; i<=n; ++i) st.insert(a[i].y);
         if ((*st.rbegin()&1)==(*st.begin()&1)){
            cout << (m-(m&1)) << '\n';
         }else{
            cout << 0 << '\n';
         }
      }else if (n==6){
         sort(a+1, a+n+1);
         pair<int, int> rect1, rect2;
         rect1.first=a[3].x-a[1].x;
         rect1.second=a[2].y-a[1].y;
         rect2.first=a[5].x-a[3].x;
         rect2.second=a[6].y-a[5].y;
         if (rect1.second&1) cout << 0 << '\n';
         else if (rect1.first&1) cout << rect1.first-1 << '\n';
         else if (rect2.second&1) cout << rect1.first << '\n';
         else if (rect2.first&1) cout << rect1.first+rect2.first-1 << '\n';
         else cout << rect1.first+rect2.first << '\n';
      }
      return 0;
   }
   vector<pair<int, int>> v;
   v.emplace_back(0, a[1].y);
   for (int i=2; i<n; ++i){
      if (a[i].y==a[i-1].y) v.back().first+=a[i].x-a[i-1].x;
      else v.emplace_back(0, v.back().second-(a[i-1].y-a[i].y));
   }
   int cur=0;
   for (auto &i:v){
      if (i.first==0 || i.second==0) continue;
      if (i.second&1){
         cout << cur << '\n';
         return 0;
      }else if (i.first&1){
         cout << cur+i.first-1 << '\n';
         return 0;
      }
      cur+=i.first;
   }
   cout << cur << '\n';
   return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 2 ms 3416 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 1 ms 3496 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 1 ms 3420 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 1 ms 3420 KB Output is correct

Subtask #2
0 / 9.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 6 ms 4064 KB Output is correct
3 Correct 27 ms 5752 KB Output is correct
4 Correct 16 ms 4568 KB Output is correct
5 Correct 14 ms 4572 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 35 ms 5736 KB Output is correct
9 Correct 17 ms 4564 KB Output is correct
10 Correct 27 ms 5584 KB Output is correct
11 Correct 14 ms 4572 KB Output is correct
12 Correct 1 ms 3420 KB Output is correct
13 Correct 29 ms 6384 KB Output is correct
14 Correct 2 ms 3416 KB Output is correct
15 Correct 1 ms 3420 KB Output is correct
16 Correct 1 ms 3420 KB Output is correct
17 Correct 1 ms 3420 KB Output is correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 16 ms 6648 KB Output is correct
3 Correct 15 ms 6520 KB Output is correct
4 Incorrect 20 ms 7120 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9432 KB Output is correct
2 Correct 17 ms 6608 KB Output is correct
3 Incorrect 2 ms 3592 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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