Submission #280326

#	Time	Username	Problem	Language	Result	Execution time	Memory
280326		spdskatr	Mixture (BOI20_mixture)	C++14	0 / 100	0 ms	256 KiB

Mixture

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cassert>
#include <cstring>

using namespace std;

int N;
int s[505], p[505], g[505], cnt = 1, cnt2 = 1, rmtime[505], rm[505], tot;
int special, rms[505];
char op[505];
int mat[3][3], adj[3][3];

int gcd(int a, int b) {
	while (b != 0) {
		int temp = b;
		b = a%b;
		a = temp;
	}
	return a;
}

void simplify(int x) {
	int v = gcd(s[x], gcd(p[x], g[x]));
	if (v > 1) {
		s[x] /= v;
		p[x] /= v;
		g[x] /= v;
	}
}

int det(int a, int b, int c) {
	return s[a] * p[b] * g[c] + s[b] * p[c] * g[a] + s[c] * p[a] * g[b]
			- s[c] * p[b] * g[a] - s[a] * p[c] * g[b] - s[b] * p[a] * g[c];
}

int works(int a, int b, int c) {
	int d = det(a, b, c);
	if (d == 0) return 0;
	// matrix
	mat[0][0] = s[a];
	mat[0][1] = s[b];
	mat[0][2] = s[c];
	mat[1][0] = p[a];
	mat[1][1] = p[b];
	mat[1][2] = p[c];
	mat[2][0] = g[a];
	mat[2][1] = g[b];
	mat[2][2] = g[c];
	// adjugate
	adj[0][0] = mat[1][1]*mat[2][2] - mat[1][2]*mat[2][1];
	adj[0][1] = mat[0][2]*mat[2][1] - mat[0][1]*mat[2][2];
	adj[0][2] = mat[0][1]*mat[1][2] - mat[0][2]*mat[1][1];
	adj[1][0] = mat[1][2]*mat[2][0] - mat[1][0]*mat[2][2];
	adj[1][1] = mat[0][0]*mat[2][2] - mat[0][2]*mat[2][0];
	adj[1][2] = mat[0][2]*mat[1][0] - mat[0][0]*mat[1][2];
	adj[2][0] = mat[1][0]*mat[2][1] - mat[1][1]*mat[2][0];
	adj[2][1] = mat[0][1]*mat[2][0] - mat[0][0]*mat[2][1];
	adj[2][2] = mat[0][0]*mat[1][1] - mat[0][1]*mat[1][0];
	// Multiply with final vector to get result
	int res[3];
	res[0] = adj[0][0] * s[0] + adj[0][1] * p[0] + adj[0][2] * g[0];
	res[1] = adj[1][0] * s[0] + adj[1][1] * p[0] + adj[1][2] * g[0];
	res[2] = adj[2][0] * s[0] + adj[2][1] * p[0] + adj[2][2] * g[0];
	if (d < 0) {
		res[0] = -res[0];
		res[1] = -res[1];
		res[2] = -res[2];
	}
	//printf("works(%d, %d, %d): %d %d %d\n", a, b, c, res[0], res[1], res[2]);
	return min(res[0], min(res[1], res[2])) >= 0;
}

int two(int t) {
	for (int i = 1; i < cnt2; i++) if (rmtime[i] > t) {
		for (int j = 1; j < i; j++) if (rmtime[j] > t) {
			if (det(i, j, 0) == 0) {
				return 1;
			}
		}
	}
	return 0;
}

void chk(int x) {
	for (int i = 1; i < x; i++) {
		for (int j = 1; j < i; j++) {
			if (works(j, i, x)) {
				//printf("triplet %d %d %d works\n", j, i, x);
				int rip = min(min(rmtime[i], rmtime[j]), rmtime[x]);
				if (rip < 6969) {
					rm[rip]++;
				}
				tot++;
			}
		}
	}
	if (s[x] == s[0] && p[x] == p[0] && g[x] == g[0]) {
		if (rmtime[x] < 6969) rms[rmtime[x]]++;
		special++;
	}
}

int main() {
	scanf("%d %d %d %d", s+0, p+0, g+0, &N);
	simplify(0);
	assert(N <= 500);
	for (int i = 1; i <= N; i++) {
		scanf(" %c", op+i);
		if (op[i] == 'A') {
			scanf("%d %d %d", s+cnt, p+cnt, g+cnt);
			simplify(cnt);
			rmtime[cnt] = 6969;
			cnt++;
		} else {
			int ng;
			scanf("%d", &ng);
			rmtime[ng] = i;
		}
	}
	for (int i = 1; i <= N; i++) {
		tot -= rm[i];
		special -= rms[i];
		if (op[i] == 'A') {
			chk(cnt2);
			cnt2++;
		}
		assert(tot >= 0 && special >= 0);
		if (special) {
			printf("1\n");
		} else if (two(i)) {
			printf("2\n");
		} else if (tot > 0) {
			printf("3\n");
		} else {
			printf("0\n");
		}
	}
}

Compilation message (stderr)

Mixture.cpp: In function 'int main()':
Mixture.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |  scanf("%d %d %d %d", s+0, p+0, g+0, &N);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |   scanf(" %c", op+i);
      |   ~~~~~^~~~~~~~~~~~~
Mixture.cpp:112:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |    scanf("%d %d %d", s+cnt, p+cnt, g+cnt);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:118:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |    scanf("%d", &ng);
      |    ~~~~~^~~~~~~~~~~

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