Submission #254783

#	Time	Username	Problem	Language	Result	Execution time	Memory
254783		model_code	Mixture (BOI20_mixture)	C++11	100 / 100	230 ms	15680 KiB

Mixture

#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 / 13
• Subtask 2: 17 / 17
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40