oj.uz

Submission #530120

# Submission time Handle Problem Language Result Execution time Memory
530120 2022-02-24T16:15:21 Z c28dnv9q3 Mixture (BOI20_mixture) C++17
0 / 100
 32 ms 292 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);
    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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 284 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 2 ms 288 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 32 ms 288 KB Output is correct
8 Incorrect 2 ms 204 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 284 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 2 ms 288 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 32 ms 288 KB Output is correct
8 Incorrect 2 ms 204 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 284 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 2 ms 288 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 32 ms 288 KB Output is correct
8 Incorrect 2 ms 204 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 284 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 2 ms 288 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 32 ms 288 KB Output is correct
8 Incorrect 2 ms 204 KB Output isn't correct
9 Halted 0 ms 0 KB -