oj.uz

Submission #254783

# Submission time Handle Problem Language Result Execution time Memory
254783 2020-07-30T15:11:48 Z model_code Mixture (BOI20_mixture) C++11
100 / 100
 230 ms 15680 KB 
#include <iostream>
#include <cstdint>
#include <map>
#include <iomanip>
#include <array>
#include <cstdio>
#include <set>

// Correct solution but it uses 128 bit integers. Works when compiling for 64bits using GCC and proably clang.

using namespace std;

const size_t MAXN = 128*1024;

using Mix = std::array<int64_t, 3>;

using i128 = __int128_t;

struct Command {
    Mix mix;
    int add;
};

Mix recipeX;
Command commands[MAXN];
int addIndex[MAXN];
size_t cmds;

using V3_128 = std::array<i128, 3>;

static Mix cross64(const Mix &a, const Mix &b) {
    Mix result;
    result[0] = a[1] * b[2] - a[2] * b[1];
    result[1] = a[2] * b[0] - a[0] * b[2];
    result[2] = a[0] * b[1] - a[1] * b[0];
    return result;
}

static int64_t dotProduct(const Mix &a, const Mix &b) {
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
}

static V3_128 cross128(const Mix &a, const Mix &b) {
    V3_128 result;
    result[0] = (i128)a[1] * b[2] - (i128)a[2] * b[1];
    result[1] = (i128)a[2] * b[0] - (i128)a[0] * b[2];
    result[2] = (i128)a[0] * b[1] - (i128)a[1] * b[0];
    return result;
}

static constexpr int sgn(i128 v) {
    return (v > 0) - (v < 0);
}

static int dir(const Mix &a, const Mix& b) {
    auto res = cross128(a, b);
    int v = sgn(res[0]);
    if (v == 0) {
        v = sgn(res[1]);
    }
    if (v == 0) {
        v = sgn(res[2]);
    }
    return v;
}

static int64_t gcd(int64_t a, int64_t b) {
    if (!b) {
        return a;
    }
    return gcd(b, a % b);
}

static Mix opposite(const Mix &a) {
    return {-a[0], -a[1], -a[2]};
}

static int64_t gcds(int64_t a, int64_t b) {
    return gcd(abs(a), abs(b));
}

static Mix normalizeMix(Mix m) {
    int64_t g = 1;
    if (m[0] == 0 && m[1] == 0) {
        g = abs(m[2]);
    } else {
        g = gcds(m[0], m[1]);
        g = gcds(g, m[2]);
    }
    return {m[0] / g, m[1] / g, m[2] / g};
}

static bool isNull(const Mix& a) {
    return a[0] == 0 && a[1] == 0 && a[2] == 0;
}

static bool sameDirection (const Mix &a, const Mix &b) {
    if (a[0] != 0) {
        return sgn(a[0]) == sgn(b[0]);
    }
    if (a[1] != 0) {
        return sgn(a[1]) == sgn(b[1]);
    }
    return sgn(a[2]) == sgn(b[2]);
}

struct CmpCircle {
    Mix p0;
    bool operator()(const Mix &a, const Mix &b) const {
        auto s1 = dir(p0, a);
        auto s2 = dir(p0, b);
        if (s1 == 0 && s2 == 0) {
            bool sd1 = sameDirection(a, p0);
            bool sd2 = sameDirection(b, p0);
            if (sd1 == sd2) {
                return false;
            } else {
                return sd1;
            }
        }
        if (s1 == 0) {
            bool sd1 = sameDirection(a, p0);
            if (sd1) {
                return true;
            }
            return dir(a, b) < 0;
        }
        if (s2 == 0) {
            bool sd2 = sameDirection(b, p0);
            if (sd2) {
                return false;
            }
            return dir(a, b) < 0;
        }
        if (s1 != s2) {
            return s1 < s2;
        }
        return dir(a, b) < 0;
    }
};

Mix chooseReference(Mix recipe)
{
    auto cross = cross64(recipe, {0, 0, 1});
    if (!isNull(cross)) {
        return cross;
    }
    cross = cross64(recipe, {0, 1, 0});
    if (!isNull(cross)) {
        return cross;
    }
    cross = cross64(recipe, {1, 0, 0});
    if (!isNull(cross)) {
        return cross;
    }
    std::cerr << "Impossible";
    std::abort();
}

static int calcCircleChange(const std::multiset<Mix, CmpCircle> &circle, decltype(circle.begin()) it, int change) {
    int ans = 0;
    auto prev = it;
    if (prev != circle.begin()) {
        --prev;
    } else {
        prev = std::prev(circle.end());
    }
    auto next = std::next(it);
    if (next == circle.end()) {
        next = circle.begin();
    }
    if (*next == *prev) {
        // case a) all 3 vectors are equal -> single 360 degree segment remains nothing changes
        // case b) split 360 not in half -> single bad segment remains
        // case c) split 360 in half -> 2 * 180 good segments
        if (*it == opposite(*next)) {
            ans -= change;
        }
    } else {
        // split
        bool oldWasBig = dir(*prev, *next) > 0;
        if (oldWasBig) {
            ans -= change;
            if (dir(*prev, *it) > 0) {
                ans += change;
            }
            if (dir(*it, *next) > 0) {
                ans += change;
            }
        } // else splitting small doesn't change anything
    }
    return ans;
}

static void solve()
{
    recipeX = normalizeMix(recipeX);
    std::map<Mix, int> normalCount;
    int readyCount = 0; // number of ready to use mixtures that match with desired one
    int count2 = 0;  // number of directions with vectors on opposite directions
    auto reference = chooseReference(recipeX);
    std::multiset<Mix, CmpCircle> circle(CmpCircle{reference});

    int badSegmentCount = 1; // number of segments larger than 180 degrees

    for (size_t i = 0; i < cmds; i++) {
        auto &cmd = commands[i];
        Mix mix;
        bool add = cmd.add > 0;
        int change = add ? 1 : -1;
        if (add) {
            mix = cmd.mix;
        } else {
            mix = commands[addIndex[-cmd.add - 1]].mix;
        }
        if (dotProduct(recipeX, mix)) { // ignore orthogonal mixes
            auto normalDirection = cross64(recipeX, mix);
            if (isNull(normalDirection)) { // keep count of parallel mixes
                readyCount += change;
            } else {
                normalDirection = normalizeMix(normalDirection);
                int thisNormalCount = (normalCount[normalDirection] += change);
                auto oppositeIt = normalCount.find(opposite(normalDirection));

                bool addFirst = add && (thisNormalCount == 1);
                bool removeLast = !add && (thisNormalCount == 0);
                if (addFirst || removeLast) {
                    bool haveOpposite = oppositeIt != normalCount.end() && oppositeIt->second > 0;
                    if (haveOpposite) {
                        count2 += change;
                    }
                }
                if (add) {
                    auto it = circle.insert(normalDirection);
                    if (circle.size() > 1) {
                       badSegmentCount += calcCircleChange(circle, it, change);
                    }
                } else {
                    if (circle.size() == 1) {
                        circle.clear();
                    } else {
                        auto it = circle.find(normalDirection);
                        badSegmentCount += calcCircleChange(circle, it, change);
                        circle.erase(it);
                    }
                }
            }    
        } // else ignore orthogonal mixes
        int result = 0;
        if (readyCount) {
            result = 1;
        } else if (count2) {
            result = 2;
        } else if (!badSegmentCount) {
            result = 3;
        }
        std::cout << result << "\n";
    }
}

static void readInput()
{
    std::cin >> recipeX[0] >> recipeX[1] >> recipeX[2];
    std::cin >> cmds;
    int mixtures = 0;
    for (size_t i = 0; i < cmds; i++) {
        char cmd;
        std::cin >> cmd;
        if (cmd == 'A') {
            std::cin >> commands[i].mix[0] >> commands[i].mix[1] >> commands[i].mix[2];
            addIndex[mixtures] = i;
            commands[i].add = ++mixtures;
        } else if (cmd == 'R') {
            std::cin >> commands[i].add;
            commands[i].add = - commands[i].add;
        } else {
            std::cerr << "unexpected command (" << cmd << ")";
        }
    }
}


int main()
{
    ios::sync_with_stdio(false);
    readInput();
    solve();
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 0 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 0 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 0 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 0 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 1 ms 512 KB Output is correct
40 Correct 1 ms 512 KB Output is correct
41 Correct 1 ms 512 KB Output is correct
42 Correct 1 ms 512 KB Output is correct
43 Correct 1 ms 512 KB Output is correct
44 Correct 1 ms 512 KB Output is correct
45 Correct 1 ms 512 KB Output is correct
46 Correct 4 ms 768 KB Output is correct
47 Correct 4 ms 768 KB Output is correct
48 Correct 2 ms 512 KB Output is correct
49 Correct 3 ms 512 KB Output is correct
50 Correct 3 ms 512 KB Output is correct
51 Correct 6 ms 896 KB Output is correct
52 Correct 5 ms 768 KB Output is correct
53 Correct 6 ms 896 KB Output is correct
54 Correct 6 ms 896 KB Output is correct
55 Correct 4 ms 640 KB Output is correct
56 Correct 6 ms 640 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 0 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 0 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 1 ms 512 KB Output is correct
40 Correct 1 ms 512 KB Output is correct
41 Correct 1 ms 512 KB Output is correct
42 Correct 1 ms 512 KB Output is correct
43 Correct 1 ms 512 KB Output is correct
44 Correct 1 ms 512 KB Output is correct
45 Correct 1 ms 512 KB Output is correct
46 Correct 4 ms 768 KB Output is correct
47 Correct 4 ms 768 KB Output is correct
48 Correct 2 ms 512 KB Output is correct
49 Correct 3 ms 512 KB Output is correct
50 Correct 3 ms 512 KB Output is correct
51 Correct 6 ms 896 KB Output is correct
52 Correct 5 ms 768 KB Output is correct
53 Correct 6 ms 896 KB Output is correct
54 Correct 6 ms 896 KB Output is correct
55 Correct 4 ms 640 KB Output is correct
56 Correct 6 ms 640 KB Output is correct
57 Correct 6 ms 640 KB Output is correct
58 Correct 12 ms 1024 KB Output is correct
59 Correct 8 ms 1024 KB Output is correct
60 Correct 8 ms 896 KB Output is correct
61 Correct 33 ms 2044 KB Output is correct
62 Correct 34 ms 2040 KB Output is correct
63 Correct 178 ms 12408 KB Output is correct
64 Correct 183 ms 12408 KB Output is correct
65 Correct 188 ms 9208 KB Output is correct
66 Correct 163 ms 9208 KB Output is correct
67 Correct 1 ms 384 KB Output is correct
68 Correct 0 ms 384 KB Output is correct
69 Correct 230 ms 15680 KB Output is correct
70 Correct 198 ms 12844 KB Output is correct
71 Correct 196 ms 12792 KB Output is correct
72 Correct 185 ms 11824 KB Output is correct
73 Correct 193 ms 12536 KB Output is correct