Submission #530120

#	Time	Username	Problem	Language	Result	Execution time	Memory
530120		c28dnv9q3	Mixture (BOI20_mixture)	C++17	0 / 100	32 ms	292 KiB

Mixture

#include <stdio.h>
#include <limits.h>

#pragma GCC optimize "trapv"

typedef long long llong;

llong square(llong x) { return x*x; }
int sign(llong x) { return (x < 0) ? -1 : (x > 0) ? 1 : 0; }

struct mixture {
    llong a, b, c;
    llong s;

    mixture() {}
    mixture(llong a, llong b, llong c) : a(a), b(b), c(c), s(a+b+c) {}
} mixtures[100005];
bool mixtureValid[100005];

int line_side(const mixture& a, const mixture& b, const mixture& x) {
    return sign(
        (a.b*b.s - a.s*b.b) * (a.a*x.s - a.s*x.a) -
        (a.a*b.s - a.s*b.a) * (a.b*x.s - a.s*x.b)
    );
}

bool can_combine(const mixture& a, const mixture& x) {
    return
        a.a*x.s == a.s*x.a &&
        a.b*x.s == a.s*x.b &&
        a.c*x.s == a.s*x.c
    ;
}

bool can_combine(const mixture& a, const mixture& b, const mixture& x) {
    if(line_side(a, b, x) != 0) return false;
    llong
        ab = (square(a.a*b.s - a.s*b.a) + square(a.b*b.s - a.s*b.b)) * x.s,
        ax = ((a.a*b.s - a.s*b.a)*(a.a*x.s - a.s*x.a) + (a.b*b.s - a.s*b.b)*(a.b*x.s - a.s*x.b)) * b.s
    ;
    if(ax < 0 || ab <= ax) return false;
    return true;
}

bool can_combine(const mixture& a, const mixture& b, const mixture& c, const mixture& x) {
    int cSab = line_side(a, b, c), bSac = line_side(a, c, b), aSbc = line_side(b, c, a);
    if(cSab == 0 || bSac == 0 || aSbc == 0) return false;
    return line_side(a, b, x) == cSab && line_side(a, c, x) == bSac && line_side(b, c, x) == aSbc;
}

int main() {
    int xA, xB, xC;
    scanf("%d %d %d", &xA, &xB, &xC);
    mixture x(xA, xB, xC);

    int N;
    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        char chr;
        for(chr = getchar(); chr != 'A' && chr != 'R'; chr = getchar());

        if(chr == 'A') {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            mixtures[i] = mixture(a, b, c);
            mixtureValid[i] = true;
        } else {
            int r;
            scanf("%d", &r);
            mixtureValid[r-1] = false;
        }

        int best = INT_MAX;
        for(int a = 0; a <= i; a++) {
            if(!mixtureValid[a]) continue;
            if(best > 1 && can_combine(mixtures[a], x)) best = 1;
            for(int b = a+1; b <= i; b++) {
                if(!mixtureValid[b]) continue;
                if(best > 2 && can_combine(mixtures[a], mixtures[b], x)) best = 2;
                for(int c = b+1; c <= i; c++) {
                    if(!mixtureValid[c]) continue;
                    if(best > 3 && can_combine(mixtures[a], mixtures[b], mixtures[c], x)) best = 3;
                }
            }
        }
        if(best == INT_MAX) best = 0;
        printf("%d\n", best);
    }

    return 0;
}

Compilation message (stderr)

Mixture.cpp: In function 'int main()':
Mixture.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d %d %d", &xA, &xB, &xC);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
Mixture.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |             scanf("%d %d %d", &a, &b, &c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:69:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |             scanf("%d", &r);
      |             ~~~~~^~~~~~~~~~

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