Submission #530121

# Submission time Handle Problem Language Result Execution time Memory
530121 2022-02-24T16:22:11 Z c28dnv9q3 Mixture (BOI20_mixture) C++17
13 / 100
2000 ms 296 KB
#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);

    int B = 0;
    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[B] = mixture(a, b, c);
            mixtureValid[B] = true;
            B++;
        } else {
            int r;
            scanf("%d", &r);
            mixtureValid[r-1] = false;
        }

        int best = INT_MAX;
        for(int a = 0; a < B; a++) {
            if(!mixtureValid[a]) continue;
            if(best > 1 && can_combine(mixtures[a], x)) best = 1;
            for(int b = a+1; b < B; b++) {
                if(!mixtureValid[b]) continue;
                if(best > 2 && can_combine(mixtures[a], mixtures[b], x)) best = 2;
                for(int c = b+1; c < B; 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

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:66:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |             scanf("%d %d %d", &a, &b, &c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |             scanf("%d", &r);
      |             ~~~~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 292 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 40 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 284 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 16 ms 296 KB Output is correct
17 Correct 16 ms 204 KB Output is correct
18 Correct 7 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 292 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 40 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 284 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 16 ms 296 KB Output is correct
17 Correct 16 ms 204 KB Output is correct
18 Correct 7 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 9 ms 204 KB Output is correct
21 Correct 1 ms 256 KB Output is correct
22 Execution timed out 2076 ms 292 KB Time limit exceeded
23 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 292 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 40 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 284 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 16 ms 296 KB Output is correct
17 Correct 16 ms 204 KB Output is correct
18 Correct 7 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 9 ms 204 KB Output is correct
21 Correct 1 ms 256 KB Output is correct
22 Execution timed out 2076 ms 292 KB Time limit exceeded
23 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 292 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 40 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 284 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 16 ms 296 KB Output is correct
17 Correct 16 ms 204 KB Output is correct
18 Correct 7 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 9 ms 204 KB Output is correct
21 Correct 1 ms 256 KB Output is correct
22 Execution timed out 2076 ms 292 KB Time limit exceeded
23 Halted 0 ms 0 KB -