Submission #254782

#	Time	Username	Problem	Language	Result	Execution time	Memory
254782		model_code	Mixture (BOI20_mixture)	C++11	100 / 100	221 ms	7288 KiB

Mixture

#include <bits/stdc++.h>
#define MAXN 100005

using namespace std;

struct vec {
	long long x, y;
	int part;
};

int crossProductResult(const vec &a, const vec &b) {
	
	__int128 res = (__int128)(a.x) * (__int128)(b.y) - (__int128)(a.y) * (__int128)(b.x);
	if (res < 0) {
		return -1;
	} else if (res > 0) {
		return 1;
	} else {
		return 0;
	}

	long long MOD = 1LL << 31;

	long long p0 = (b.y % MOD) * (a.x % MOD);
	long long p1 = (b.y % MOD) * (a.x / MOD) + (a.x % MOD) * (b.y / MOD);
	long long p2 = (a.x / MOD) * (b.y / MOD);
	long long p3 = 0;
	p1 += p0 / MOD;
	p0 %= MOD;
	p2 += p1 / MOD;
	p1 %= MOD;
	p3 += p2 / MOD;
	p2 %= MOD;

	long long q0 = (b.x % MOD) * (a.y % MOD);
	long long q1 = (b.x % MOD) * (a.y / MOD) + (a.y % MOD) * (b.x / MOD);
	long long q2 = (a.y / MOD) * (b.x / MOD);
	long long q3 = 0;
	q1 += q0 / MOD;
	q0 %= MOD;
	q2 += q1 / MOD;
	q1 %= MOD;
	q3 += q2 / MOD;
	q2 %= MOD;

	if (p3 < q3) {
		return -1;
	} else if (p3 > q3) {
		return 1;
	} else {
		if (p2 < q2) {
			return -1;
		} else if (p2 > q2) {
			return 1;
		} else {
			if (p1 < q1) {
				return -1;
			} else if (p1 > q1) {
				return 1;
			} else {
				if (p0 < q0) {
					return -1;
				} else if (p0 > q0) {
					return 1;
				} else {
					return 0;
				}
			}
		}
	}
}

int vecCompare(const vec &a, const vec &b) {
	if (a.part < b.part) {
		return -1;
	} else if (a.part > b.part) {
		return 1;
	} else {
		return crossProductResult(a, b);
	}
}

vec negateVec(const vec &a) {
	vec res;
	res.x = -a.x;
	res.y = -a.y;
	res.part = 1 ^ a.part;
	return res; 
}

struct vecLess {
	bool operator()(const vec &lhs, const vec &rhs) {
		return vecCompare(lhs, rhs) < 0;
	}
};

vec newVector(long long x, long long y) {
	vec res;
	res.x = x;
	res.y = y;
	if (x == 0) {
		if (y > 0) {
			res.part = 0;
		} else if (y < 0) {
			res.part = 1;
		} else {
			res.part = -1;
		}
	} else if (x > 0) {
		res.part = 0;
	} else {
		res.part = 1;
	}
	return res;
}

int main () {
	long long S, P, G;
	scanf("%lli %lli %lli",&S,&P,&G);

	int N;
	scanf("%d",&N);

	static vec data[MAXN];
	int datac = 0;
	multiset<vec, vecLess> st;

	int amountOfDots = 0;
	int amountOfLines = 0;
	int amountOfEmptyPies = 1;

	for (int i = 0; i < N; i++) {
		char c;
		scanf("\n%c",&c);
		if (c == 'A') {
			long long s, p, g;
			scanf("%lli %lli %lli",&s,&p,&g);

			long long x = s * (S + P + G) - S * (s + p + g);
			long long y = p * (S + P + G) - P * (s + p + g);

			if ((x == 0) && (y == 0)) {
				data[datac] = newVector(0, 0);
				datac++;
				amountOfDots++;
			} else {
				long long mult = s + p + g;
				vec cur = newVector(mult * x, mult * y);
				data[datac] = cur;
				datac++;

				multiset<vec>::iterator same = st.find(cur);
				multiset<vec>::iterator opposite = st.find(negateVec(cur));
				if ((same == st.end()) && (opposite != st.end())) {
					amountOfLines++;
				}

				if (st.size() >= 2) {
					multiset<vec>::iterator nextIt = st.upper_bound(cur);
					vec next;
					if (nextIt == st.end()) {
						next = *st.begin();
					} else {
						next = *nextIt;
					}
					vec prev;
					if ((nextIt == st.end()) || (nextIt == st.begin())) {
						prev = *st.rbegin();
					} else {
						prev = *(--nextIt);
					}

					if ((crossProductResult(prev, next) > 0)
							&& (crossProductResult(prev, cur) <= 0)
							&& (crossProductResult(cur, next) <= 0)) {
						amountOfEmptyPies = 0;
					}
				} else {
					amountOfEmptyPies = 1;
				}

				st.insert(cur);
			}
		} else {
			int ind;
			scanf("%d",&ind);
			vec cur = data[ind - 1];

			if ((cur.part == -1)) {
				amountOfDots--;
			} else {
				st.erase(st.find(cur));

				multiset<vec>::iterator same = st.find(cur);
				multiset<vec>::iterator opposite = st.find(negateVec(cur));
				if ((same == st.end()) && (opposite != st.end())) {
					amountOfLines--;
				}

				if (st.size() >= 2) {
					multiset<vec>::iterator nextIt = st.upper_bound(cur);
					vec next;
					if (nextIt == st.end()) {
						next = *st.begin();
					} else {
						next = *nextIt;
					}
					vec prev;
					if ((nextIt == st.end()) || (nextIt == st.begin())) {
						prev = *st.rbegin();
					} else {
						prev = *(--nextIt);
					}

					if (crossProductResult(prev, next) > 0) {
						amountOfEmptyPies = 1;
					}
				} else {
					amountOfEmptyPies = 1;
				}
			}
		}
		if (amountOfDots > 0) {
			printf("1\n");
		} else if (amountOfLines > 0) {
			printf("2\n");
		} else if (amountOfEmptyPies == 0) {
			printf("3\n");
		} else {
			printf("0\n");
		}
	}

	return 0;
}

Compilation message (stderr)

Mixture.cpp: In function 'int main()':
Mixture.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lli %lli %lli",&S,&P,&G);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
Mixture.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n%c",&c);
   ~~~~~^~~~~~~~~~~
Mixture.cpp:137:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lli %lli %lli",&s,&p,&g);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:186:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&ind);
    ~~~~~^~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40