QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#295982 | #4833. Tetra-puzzle | ucup-team1447 | 0 | 11ms | 265828kb | C++14 | 5.0kb | 2024-01-01 20:30:59 | 2024-01-01 20:30:59 |
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];
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;
}
Details
Tip: Click on the bar to expand more detailed information
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