QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#293159 | #4833. Tetra-puzzle | ucup-team1447# | 0 | 12ms | 134768kb | C++14 | 4.6kb | 2023-12-28 22:24:19 | 2023-12-28 22:24:19 |
Judging History
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] * 4 + p[2] * 3 + p[3] * 2 + p[4] * 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;
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 (rnd()%(A+B)<A)
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: 12ms
memory: 134768kb
First Run Input
prepare 6 TO LO ZI LI LT LT
First Run Output
OOIITL
Second Run Input
play 6 O O I I T L
Second Run Output
**... **... ..... ..... ..... ##.** ##.** ..... ..... ..... ##*## ##*## ..*.. ..*.. ..... ..... ..... ..#.. ..#.. ****. .***. ..*.. ..#.. ..#.. ####. .#.#. .*... .*... **... ##.#.
result:
ok good job!
Test #2:
score: 100
Accepted
time: 0ms
memory: 134536kb
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: 134536kb
First Run Input
prepare 10 LO TZ ZO OI OL ZL ZO TL OZ LO
First Run Output
OZOOOLZTOO
Second Run Input
play 10 O Z O O O
Second Run Output
**... **... ..... ..... ..... ##**. ##.** ..... ..... ..... ####. ##.## ..... **... **... ####. ##.## ..... ##.** ##.** ####. ##.## ..... ##.## ##.##
result:
wrong answer wrong answer: invalid set [B] on step 5