QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293166#4833. Tetra-puzzleucup-team1447#0 8ms134836kbC++144.6kb2023-12-28 22:27:012023-12-28 22:27:01

Judging History

你现在查看的是最新测评结果

  • [2023-12-28 22:27:01]
  • 评测
  • 测评结果:0
  • 用时:8ms
  • 内存:134836kb
  • [2023-12-28 22:27:01]
  • 提交

answer

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
const char s[] = {'I', 'L', 'O', 'T', 'Z'};
const int v[4][2] = {{+1, 0}, {0, +1}, {-1, 0}, {0, -1}};
const int xx[5][4] = {
    {0, 0, 0, 0},
    {0, 0, 0, 1},
    {0, 0, 1, 1},
    {0, 1, 1, 2},
    {0, 1, 1, 2}};
const int yy[5][4] = {
    {0, 1, 2, 3},
    {0, 1, 2, 2},
    {0, 1, 1, 0},
    {0, 0, 1, 0},
    {0, 0, 1, 1}};
int get(char c) { return std::find(s, s + 5, c) - s; }
bool able(int A, int B)
{
    int X = B >> 7 & 7, Y = B >> 4 & 7, Sx = B >> 2 & 3, Sy = B & 3, add = 0;
    if (Sx % 2 == Sy % 2)
        return false;
    for (int i = 0; i != 4; ++i)
    {
        int tx = X + xx[A][i] * v[Sx][0] + yy[A][i] * v[Sy][0], ty = Y + xx[A][i] * v[Sx][1] + yy[A][i] * v[Sy][1];
        if (tx < 0 || tx >= 5 || ty < 0 || ty >= 5)
            return false;
        add |= 1 << (tx * 5 + ty);
    }
    return true;
}
int fill(int A, int B)
{
    int X = B >> 7 & 7, Y = B >> 4 & 7, Sx = B >> 2 & 3, Sy = B & 3, res = 0;
    assert(Sx % 2 != Sy % 2);
    for (int i = 0; i != 4; ++i)
    {
        int tx = X + xx[A][i] * v[Sx][0] + yy[A][i] * v[Sy][0], ty = Y + xx[A][i] * v[Sx][1] + yy[A][i] * v[Sy][1];
        assert(0 <= tx && tx < 5 && 0 <= ty && ty < 5);
        res |= 1 << (tx * 5 + ty);
    }
    return res;
}
int clear(int A)
{
    int del = 0;
    for (int i = 0, j = 0b0000100001000010000100001; i != 5; ++i, j <<= 1)
        if ((A & j) == j)
            del |= j;
    for (int i = 0, j = 0b0000000000000000000011111; i != 5; ++i, j <<= 5)
        if ((A & j) == j)
            del |= j;
    return A ^ del;
}
void print(int A, int B)
{
    for (int i = 0; i != 5; ++i, std::cout << std::endl)
        for (int j = 0; j != 5; ++j)
            std::cout << (B >> (i * 5 + j) & 1 ? (A >> (i * 5 + j) & 1 ? '#' : '*') : '.');
}
std::vector<int> to[5];
int r[1 << 25];
int eval(int x)
{
    if (r[x] >= 0)
        return r[x];
    std::vector<int> p(5);
    for (int i = 0; i != 5; ++i)
        for (auto j : to[i])
            p[i] += !(x & j);
    std::sort(p.begin(), p.end());
    return r[x] = p[1] * 12 + p[2] * 6 + p[3] * 4 + p[4] * 3;
}
int tmp;
int trans(int A, int B)
{
    int bes = (1 << 25) - 1;
    for (auto i : to[B])
    {
        if (A & i)
            continue;
        int lst = A | i;
        int nxt = clear(A | i);
        if (eval(bes) < eval(nxt))
            bes = nxt, tmp = lst;
    }
    return bes;
}
std::string who;
int n;
signed main()
{
    std::memset(r, -1, sizeof(r));
    std::ios::sync_with_stdio(false);
    for (int i = 0; i != 5; ++i)
        for (int j = 0; j != 1 << 10; ++j)
            if (able(i, j))
                to[i].push_back(fill(i, j));
    for (int i = 0; i != 5; ++i)
    {
        std::sort(to[i].begin(), to[i].end());
        to[i].erase(std::unique(to[i].begin(), to[i].end()), to[i].end());
    }
    // for (int i = 0; i != 1 << 25; ++i)
    // {
    //     if (clear(i) != i)
    //         continue;
    //     r[i] = eval(i);
    // }
    // std::queue<int> que;
    // que.push(0);
    // while (!que.empty())
    // {
    //     int now = que.front();
    //     que.pop();
    //     std::vector<int> p;
    //     for (int t = 0; t != 5; ++t)
    //     {
    //         int bes = -1, val = -1;
    //         for (auto i : to[t])
    //             if (!(now & i) && r[clear(now | i)] > val)
    //                 bes = clear(now | i), val = r[clear(now | i)];
    //         if (bes != -1)
    //             p.push_back(bes), std::cout << t << std::endl;
    //     }
    //     print(now, now);
    //     assert(p.size() >= 4);
    //     std::sort(p.begin(), p.end(), [&](const int &A, const int &B)
    //               { return r[A] > r[B]; });
    //     for (int i = 0; i != 4; ++i)
    //         que.push(p[i]);
    // }
    // return 0;
    std::cin >> who;
    std::mt19937_64 rnd(time(0));
    if (who == "prepare")
    {
        std::cin >> n;
        int cur = 0;
        for (int i = 0; i != n; ++i)
        {
            static char a, b;
            std::cin >> a >> b;
            int A = trans(cur, get(a)), B = trans(cur, get(b));
            if (r[A]<r[B])
                std::cout << a, cur = A;
            else
                std::cout << b, cur = B;
        }
    }
    if (who == "play")
    {
        std::cin >> n;
        int cur = 0;
        for (int i = 0; i != n; ++i)
        {
            static char c;
            std::cin >> c;
            int C = trans(cur, get(c));
            print(cur, tmp);
            cur = C;
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 134836kb

First Run Input

prepare
6
TO LO ZI LI LT LT

First Run Output

TOZITT

Second Run Input

play
6
T
O
Z
I
T
T

Second Run Output

***..
.*...
.....
.....
.....
###**
.#.**
.....
.....
.....
.....
.#.##
....*
...**
...*.
.....
.#.##
****#
...##
...#.
.....
.#.##
.....
***##
.*.#.
.***.
.#*##
.....
.....
.#.#.

result:

ok good job!

Test #2:

score: 100
Accepted
time: 7ms
memory: 134708kb

First Run Input

prepare
1
ZI

First Run Output

Z

Second Run Input

play
1
Z

Second Run Output

.**..
**...
.....
.....
.....

result:

ok good job!

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 134712kb

First Run Input

prepare
10
LO TZ ZO OI OL ZL ZO TL OZ LO

First Run Output

OZOOOLOLZO

Second Run Input

play
10
O
Z
O
O
O

Second Run Output

**...
**...
.....
.....
.....
##**.
##.**
.....
.....
.....
####.
##.##
.....
**...
**...
####.
##.##
.....
##.**
##.**
####.
##.##
.....
##.##
##.##

result:

wrong answer wrong answer: invalid set [B] on step 5