icpc_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ebi-fly13/icpc_library

:heavy_check_mark: test/misc/aoj_1197.test.cpp

Depends on

Code

#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1197&lang=en"

#include "../../misc/dice.hpp"
#include "../../template/template.hpp"

bool input(std::vector<int> &t) {
    int zero = 0;
    rep(i, 0, 6) {
        std::cin >> t[i];
        if (t[i] == 0) zero++;
    }
    if (zero == 6) return false;
    return true;
}

using namespace lib;

int main() {
    std::vector<int> t(6);
    while (input(t)) {
        int sum = 0;
        rep(i, 0, 6) sum += t[i];
        int p, q;
        std::cin >> p >> q;
        p--;
        std::vector<int> idxs(6);
        std::iota(all(idxs), 0);
        std::string ans = "";
        do {
            std::vector<int> val(6);
            rep(i, 0, 6) val[i] = t[idxs[i]];
            Dice dice;
            dice.set_val(val);
            auto check = [&]() -> bool {
                int na = dice.top_val() + dice.down_val();
                int nb = dice.left_val() + dice.right_val();
                int nc = dice.front_val() + dice.back_val();
                return dice.top_val() >= 0 && na <= nb + nc &&
                       nb <= 1 + nc + na && nc <= 1 + na + nb;
            };
            if (!check()) {
                continue;
            }
            std::string s = "";
            rep(_, 0, sum) {
                {
                    dice.rollE();
                    dice.val[dice.up]--;
                    if (check()) {
                        s += 'E';
                        continue;
                    }
                    dice.val[dice.up]++;
                    dice.rollW();
                }
                {
                    dice.rollN();
                    dice.val[dice.up]--;
                    if (check()) {
                        s += 'N';
                        continue;
                    }
                    dice.val[dice.up]++;
                    dice.rollS();
                }
                {
                    dice.rollS();
                    dice.val[dice.up]--;
                    if (check()) {
                        s += 'S';
                        continue;
                    }
                    dice.val[dice.up]++;
                    dice.rollN();
                }
                {
                    dice.rollW();
                    dice.val[dice.up]--;
                    if (check()) {
                        s += 'W';
                        continue;
                    }
                    dice.val[dice.up]++;
                    dice.rollE();
                }
                assert(0);
            }
            if (ans.empty())
                ans = s;
            else
                chmin(ans, s);
        } while (std::next_permutation(all(idxs)));
        if (ans.empty()) {
            std::cout << "impossible\n";
            continue;
        }
        std::cout << ans.substr(p, q - p) << '\n';
    }
}
#line 1 "test/misc/aoj_1197.test.cpp"
#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1197&lang=en"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 2 "misc/dice.hpp"

namespace lib {

struct Dice {
    int up = 0, front = 1, right = 2, left = 3, back = 4, down = 5;

    Dice() = default;

    void set_val(const std::vector<int> &_val) {
        assert(int(_val.size()) == 6);
        val = _val;
    }

    // y++
    void rollN() {
        int buff = down;
        down = back;
        back = up;
        up = front;
        front = buff;
    }

    // y--
    void rollS() {
        int buff = down;
        down = front;
        front = up;
        up = back;
        back = buff;
    }

    // x++
    void rollE() {
        int buff = down;
        down = right;
        right = up;
        up = left;
        left = buff;
    }

    // x--
    void rollW() {
        int buff = down;
        down = left;
        left = up;
        up = right;
        right = buff;
    }

    // 右回転(時計回り)
    void rollR() {
        int buff = right;
        right = back;
        back = left;
        left = front;
        front = buff;
    }

    // 左回転(反時計回り)
    void rollL() {
        int buff = left;
        left = back;
        back = right;
        right = front;
        front = buff;
    }

    void roll(char c) {
        if (c == 'N')
            rollN();
        else if (c == 'S')
            rollS();
        else if (c == 'E')
            rollE();
        else if (c == 'W')
            rollW();
        else if (c == 'R')
            rollR();
        else if (c == 'L')
            rollL();
        else
            assert(0);
    }

    int top_val() const {
        return val[up];
    }

    int right_val() const {
        return val[right];
    }

    int left_val() const {
        return val[left];
    }

    int front_val() const {
        return val[front];
    }

    int back_val() const {
        return val[back];
    }

    int down_val() const {
        return val[down];
    }

    std::vector<int> now() const {
        std::vector<int> ret(6);
        ret[0] = top_val();
        ret[1] = front_val();
        ret[2] = right_val();
        ret[3] = left_val();
        ret[4] = back_val();
        ret[5] = down_val();
        return ret;
    }

    std::vector<Dice> makeDice() const {
        std::vector<Dice> ret;
        for (int i = 0; i < 6; i++) {
            Dice d(*this);
            if (i == 1) d.rollN();
            if (i == 2) d.rollS();
            if (i == 3) {
                d.rollS();
                d.rollS();
            }
            if (i == 4) d.rollL();
            if (i == 5) d.rollR();
            for (int j = 0; j < 4; j++) {
                ret.emplace_back(d);
                d.rollE();
            }
        }
        return ret;
    }

    std::vector<int> val = {0, 1, 2, 3, 4, 5};
};

}
#line 6 "test/misc/aoj_1197.test.cpp"

bool input(std::vector<int> &t) {
    int zero = 0;
    rep(i, 0, 6) {
        std::cin >> t[i];
        if (t[i] == 0) zero++;
    }
    if (zero == 6) return false;
    return true;
}

using namespace lib;

int main() {
    std::vector<int> t(6);
    while (input(t)) {
        int sum = 0;
        rep(i, 0, 6) sum += t[i];
        int p, q;
        std::cin >> p >> q;
        p--;
        std::vector<int> idxs(6);
        std::iota(all(idxs), 0);
        std::string ans = "";
        do {
            std::vector<int> val(6);
            rep(i, 0, 6) val[i] = t[idxs[i]];
            Dice dice;
            dice.set_val(val);
            auto check = [&]() -> bool {
                int na = dice.top_val() + dice.down_val();
                int nb = dice.left_val() + dice.right_val();
                int nc = dice.front_val() + dice.back_val();
                return dice.top_val() >= 0 && na <= nb + nc &&
                       nb <= 1 + nc + na && nc <= 1 + na + nb;
            };
            if (!check()) {
                continue;
            }
            std::string s = "";
            rep(_, 0, sum) {
                {
                    dice.rollE();
                    dice.val[dice.up]--;
                    if (check()) {
                        s += 'E';
                        continue;
                    }
                    dice.val[dice.up]++;
                    dice.rollW();
                }
                {
                    dice.rollN();
                    dice.val[dice.up]--;
                    if (check()) {
                        s += 'N';
                        continue;
                    }
                    dice.val[dice.up]++;
                    dice.rollS();
                }
                {
                    dice.rollS();
                    dice.val[dice.up]--;
                    if (check()) {
                        s += 'S';
                        continue;
                    }
                    dice.val[dice.up]++;
                    dice.rollN();
                }
                {
                    dice.rollW();
                    dice.val[dice.up]--;
                    if (check()) {
                        s += 'W';
                        continue;
                    }
                    dice.val[dice.up]++;
                    dice.rollE();
                }
                assert(0);
            }
            if (ans.empty())
                ans = s;
            else
                chmin(ans, s);
        } while (std::next_permutation(all(idxs)));
        if (ans.empty()) {
            std::cout << "impossible\n";
            continue;
        }
        std::cout << ans.substr(p, q - p) << '\n';
    }
}
Back to top page