Submission #1022039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022039		huutuan	Tiles (BOI24_tiles)	C++14	15 / 100	35 ms	9432 KiB

Main

#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 / 4
• Subtask 2: 0 / 9
• Subtask 3: 11 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 22
• Subtask 6: 0 / 25
• Subtask 7: 0 / 10