QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#295982#4833. Tetra-puzzleucup-team14470 11ms265828kbC++145.0kb2024-01-01 20:30:592024-01-01 20:30:59

Judging History

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

  • [2024-01-01 20:30:59]
  • 评测
  • 测评结果:0
  • 用时:11ms
  • 内存:265828kb
  • [2024-01-01 20:30:59]
  • 提交

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];
double r[1 << 25];
double 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] * 0.4 + p[2] * 0.3 + p[3] * 0.2 + p[4] * 0.1;
}
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;
    if (who == "prepare")
    {
        std::cin >> n;
        int cur = 0;
        for (int i = 0; i != n; ++i)
        {
            static char a, b;
            std::cin >> a >> b;
            if(a=='T'||b=='T')std::cout<<(char)(rand()%4?'T':a^b^'T');else
            if(a=='Z'||b=='Z')std::cout<<(char)(rand()%4?'Z':a^b^'Z');else
            if(a=='L'||b=='L')std::cout<<(char)(rand()%4?'L':a^b^'L');else
            if(a=='I'||b=='I')std::cout<<(char)(rand()%4?'I':a^b^'I');else
            if(a=='O'||b=='O')std::cout<<(char)(rand()%4?'O':a^b^'O');else
            {}
            continue;
            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;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 265828kb

First Run Input

prepare
6
TO LO ZI LI LT LT

First Run Output

TLZLTT

Second Run Input

play
6
T
L
Z
L
T
T

Second Run Output

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

result:

ok good job!

Test #2:

score: 100
Accepted
time: 11ms
memory: 265672kb

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: 100
Accepted
time: 3ms
memory: 265764kb

First Run Input

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

First Run Output

LTZILZZLZL

Second Run Input

play
10
L
T
Z
I
L
Z
Z
L
Z
L

Second Run Output

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

result:

ok good job!

Test #4:

score: 100
Accepted
time: 11ms
memory: 265780kb

First Run Input

prepare
29
ZT OT ZL LT ZI LO IZ LT OI ZT ZT OL ZI LT LZ TZ IL ZI OT LZ LT LZ OT OI IO OZ IZ ZL ZL

First Run Output

TTZTZLZLITTLZTZTIZOLTLTIIZZZZ

Second Run Input

play
29
T
T
Z
T
Z
L
Z
L
I
T
T
L
Z
T
Z
T
I
Z
O
L
T
L
T
I
I
Z
Z
Z
Z

Second Run Output

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

result:

ok good job!

Test #5:

score: 0
Wrong Answer
time: 11ms
memory: 265700kb

First Run Input

prepare
36
TI ZT IT IT OT OZ IL TZ ZO LO LZ ZL OT ZI IL OT OT ZI ZT TZ TI LT LO OL IL OL IZ OZ OL ZL LT IO ZO ZL ZO LT

First Run Output

TTTTTZLZZLZZTZLTOZZZTLLLLLZZLZTIZZZT

Second Run Input

play
36
T
T
T
T
T
Z
L
Z
Z
L
Z
Z
T
Z
L
T
O
Z
Z
Z

Second Run Output

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

result:

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