QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#293145 | #4833. Tetra-puzzle | ucup-team1447# | 0 | 16ms | 134640kb | C++14 | 4.6kb | 2023-12-28 22:19:56 | 2023-12-28 22:19:57 |
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] = 100000 + (p[1] + 1) * (p[2] + 1) * (p[3] + 1) * (p[4] + 1) - __builtin_popcount(x) * 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;
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: 0ms
memory: 134556kb
First Run Input
prepare 6 TO LO ZI LI LT LT
First Run Output
OLIILL
Second Run Input
play 6 O L I I L L
Second Run Output
**... **... ..... ..... ..... ##..* ##*** ..... ..... ..... ##..# .*... .*... .*... .*... #...# *.... *.... *.... *.... ***.# *.... ..... ..... ..... ###.# #.... *.... *.... **...
result:
ok good job!
Test #2:
score: 100
Accepted
time: 0ms
memory: 134572kb
First Run Input
prepare 1 ZI
First Run Output
I
Second Run Input
play 1 I
Second Run Output
****. ..... ..... ..... .....
result:
ok good job!
Test #3:
score: 100
Accepted
time: 4ms
memory: 134508kb
First Run Input
prepare 10 LO TZ ZO OI OL ZL ZO TL OZ LO
First Run Output
LTZILLZLZL
Second Run Input
play 10 L T Z I L L Z L Z L
Second Run Output
***.. *.... ..... ..... ..... ###.. #.... *.... **... *.... *##.. **... .*... .#... ..... ###.. ##... .#... .#... ****. #.#.. #**.. ..*.. ..*.. #.##. #...* ##*** ..... ..... #..#. #...# ..... ..... **... #**#. #...# ..... ..... ##*** ####* #**.# **... ..... ..... ..... ###.# ##... .*... .*... **...
result:
ok good job!
Test #4:
score: 100
Accepted
time: 8ms
memory: 134544kb
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
TTZLILILITTLILLTLZTLLLTIIZZLL
Second Run Input
play 29 T T Z L I L I L I T T L I L L T L Z T L L L T I I Z Z L L
Second Run Output
***.. .*... ..... ..... ..... ###.. .#... .*... **... .*... #*#.. **... *.... #.... ..... ###.. ##... #*... #*... **... ..#.. ..*.. ..*.. ..*.. ..*.. ***.. *.... ..... ..... ..... ###.. #.*.. ..*.. ..*.. ..*.. ##*** #...* ..... ..... ..... ****. #...# ..... ..... ..... ####. #***# ..*.. ..... ..... ...
result:
ok good job!
Test #5:
score: 100
Accepted
time: 16ms
memory: 134576kb
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
ITTITOLZOLLLTIIOTITTILOLILIOLLLIOLOL
Second Run Input
play 36 I T T I T O L Z O L L L T I I O T I T T I L O L I L I O L L L I O L O L
Second Run Output
****. ..... ..... ..... ..... ####* ...** ....* ..... ..... .*... ***## ....# ..... ..... .#... ..... ****# ..... ..... *#... **... *.... ..... ..... ##... ##... #.... **... **... *#... *#... **... .#... .#... #.... #.... #*... **... *.... **... **... .#... .#... ..... ##... ##... *#... *#... **... ...
result:
ok good job!
Test #6:
score: 100
Accepted
time: 8ms
memory: 134624kb
First Run Input
prepare 57 LT OI TL IZ OT TL LT TI LO LT LO LO OL IO LI IT TZ TZ IO ZT TI OT OI TL TL ZT TZ OL OI LI OZ ZI TO LZ IO IO LT OZ TO OZ IZ TZ LT ZO TO TZ OT LT ZO OL IL LO ZT OZ OL IL ZI
First Run Output
LILITLLTLLLLLIIITTITTTILLZZLIIOZTZIITOTOITTOTZTLOLLLZZLLI
Second Run Input
play 57 L I L I T L L T L L L L L I I I T T I T T T I L L Z Z L I I O Z T Z I I T O T O I T T O T Z T L O L L L Z Z L L I
Second Run Output
***.. *.... ..... ..... ..... ###.. #.*.. ..*.. ..*.. ..*.. ##*** #...* ..... ..... ..... ****. #...# ..... ..... ..... ####. #***# ..*.. ..... ..... ####* ....* ..#** ..... ..... *.... *...# **### ..... ..... #.*.. #***# ..... ..... ..... #.#** ....* ....* ..... ..... #.### ....# ....# ....* ..*** ...
result:
ok good job!
Test #7:
score: 100
Accepted
time: 0ms
memory: 134552kb
First Run Input
prepare 88 ZL OL OT IT LO ZL OI ZT TO OI OL OL LZ ZT TL TZ IO ZL TZ TO IL LO ZT OL LT ZI TZ IL LT ZL OT TI ZO ZO ZT OZ TL TL LO OI TO OZ LI ZO ZT ZT IO IZ OZ ZO ZI ZO IO IO TI OL IL IT IL TL TL ZL IT IT ZO IO OL IL ZI TO OL IL ZI LZ LT IL LI ZO IL TL IT LI ZI OL TO OZ IZ OZ
First Run Output
LLTILLITTILLZTLZILZTIOTLTITILLTIOZTOLLLITZLZTTIIZZIOIOILIIITTZIIOILIIOLIILLLIOLLIIILOOIO
Second Run Input
play 88 L L T I L L I T T I L L Z T L Z I L Z T I O T L T I T I L L T I O Z T O L L L I T Z L Z T T I I Z Z I O I O I L I I I T T Z I I O I L I I O L I I L L L I O L L I I I L O O I O
Second Run Output
***.. *.... ..... ..... ..... ###** #...* ....* ..... ..... ..*.. #***# ....# ..... ..... ..#.. ..... ****# ..... ..... **#.. *.... *.... ..... ..... ###** #...* #...* ..... ..... ****. #...# #...# ..... ..... ####. #.*.# #***# ..... ..... ####. #.#.# ..*.. .**.. ..*.. ##.#. #..*# ...*. .#.*. ...*. ...
result:
ok good job!
Test #8:
score: 100
Accepted
time: 0ms
memory: 134576kb
First Run Input
prepare 105 LI LI OI TL OZ LZ IL IZ IL TI IL IO OT LT LO ZO LI LZ OI IL ZT IT LZ IZ IZ LI IT LI IO TI ZL OI IT LO TZ OI IL OL IL OT IL OZ LT IO OL OL LO ZO TI LI LI LI ZO ZI LI OL TI TZ LO LT IL LZ IL OL ZT LT IZ IL TZ IT OZ TL ZI IZ IZ TO IT IO TO TI TO TZ ZT IZ LI IL ZI TI TL TZ TO LI LO OL IL IL ...
First Run Output
IIILOLIIIIIIOLLZIZIITTZIILIIIILIILTILLLOIZLILLLOILLIZILOITLLILILTLIITIZLZIITIIOTTTTILLIILTTLLLIITOLLOIIIL
Second Run Input
play 105 I I I L O L I I I I I I O L L Z I Z I I T T Z I I L I I I I L I I L T I L L L O I Z L I L L L O I L L I Z I L O I T L L I L I L T L I I T I Z L Z I I T I I O T T T T I L L I I L T T L L L I I T O L L O I I I L
Second Run Output
****. ..... ..... ..... ..... ####. ...*. ...*. ...*. ...*. ###.. ..*.. ..*.. ..*.. ..*.. ##*** ....* ..... ..... ..... ..... ....# ..... ...** ...** ...** ...*# ...*. ...## ...## ....# ****# ..... ....# ....# ....# ..... ..... ****# ....# ****# ..... ..... ..... ....# ....* ....* ....* ....* ....# ...
result:
ok good job!
Test #9:
score: 100
Accepted
time: 7ms
memory: 134640kb
First Run Input
prepare 204 TZ TL OL TL ZO OT ZO LI TZ IO TI OL LZ TI TO ZT IL OI LT IT OZ TI OT TI ZL ZI ZO TI OI ZI TL LI ZI IO TI ZL LZ OL ZI TZ OI OI IZ LO IL LO IZ ZT ZT OL ZI OZ TL OI TI IT IZ ZL TI OI LZ OI TZ IZ IO OZ ZI TO OT TI TO IO IZ OI TZ LT TZ ZI OL LO LO OZ LO ZL LZ TZ LT TO OL LO LT TZ TL OZ ZO LO ...
First Run Output
TLLLOTZLTITLZITTIILIOTTTLIOIIILIIIILLLITIOILLLIZTLIZLIIIILIILITIIZIOTTTIIIZLZILLLZLLLTLTLLTTLOOLZLTITITLLTLILTITOIIILOTITZTIZTZIILLLZZIIIITLTTLTLILLOILITTLIILIOILLILOLOZIOTLZITLZTILLIIILITILIIZILLLTLLTLTL
Second Run Input
play 204 T L L L O T Z L T I T L Z I T T I I L I O T T T L I O I I I L I I I I L L L I T I O I L L L I Z T L I Z L I I I I L I I L I T I I Z I O T T T I I I Z L Z I L L L Z L L L T L T L L T T L O O L Z L T I T I T L L T L I L T I T O I I I L O T I T Z T I Z T Z I I L L L Z Z I I I I T L T T L T L I...
Second Run Output
***.. .*... ..... ..... ..... ###.. .#... .*... .*... **... #.#.. **... *.... *.... #.... **#.. *#... *.... ..... ..... ###** ##.** #.... ..... ..... .***. ##*## #.... ..... ..... *###. **... #*... ..... ..... ####* ##*** ##... ..... ..... ..... ...*. ##*** ..... ..... .**** ...#. ..... ..... ..... ...
result:
ok good job!
Test #10:
score: 100
Accepted
time: 3ms
memory: 134512kb
First Run Input
prepare 303 ZT ZT IO ZL LT TI LO LZ TI ZT TI ZT LO OZ ZT TL IT TZ ZI IL TL OZ IO OT ZT TI LT ZT ZL ZL IO LZ IZ IZ ZT TZ OT OI LZ IL IZ TL IT ZO TL ZL IZ IZ LO LO ZI TI OT ZT OI IT ZI IL OI TO ZL LI TL LT OI LZ TI TZ OL ZO OZ IL LO ZT ZL IT TO ZI TZ IL IO LO LT IT OL LO ZT OZ OI TI OL OZ ZI IT IO IT ...
First Run Output
TTIZLILLTTITLZZLITILTOITTTTTLLILZIZTTILIITTOLLZILLITTTITIIIOLILLILITLZOLLTLIOZTLILLILLTZIILZZIIIILILTTLTLLTLLIZLOTTLZOILTILZILZTOTIZIOIIIILLIOIITLLLLILILOTILIIIITTOTITLLILILLLLLLILZZLIIIIIOTOLOLZLLZLLTITZLITTOTLLLITTITLIOLIZTOZILTOITZLLLILILOLIOLIIOLLLTILLLLTIIIIILTTLLTIILILLIIOILOLOTLZIIITIILTILLZTTLT
Second Run Input
play 303 T T I Z L I L L T T I T L Z Z L I T I L T O I T T T T T L L I L Z I Z T T I L I I T T O L L Z I L L I T T T I T I I I O L I L L I L I T L Z O L L T L I O Z T L I L L I L L T Z I I L Z Z I I I I L I L T T L T L L T L L I Z L O T T L Z O I L T I L Z I L Z T O T I Z I O I I I I L L I O I I T L...
Second Run Output
***.. .*... ..... ..... ..... ###.. .#... .*... **... .*... #.#.. ..*.. ..*.. #.*.. ..*.. #*... **... *.... #.... ..... ##... ##... #*... #*... **... ****. ..... ..... ..... ..... ####* ....* ...** ..... ..... ..... *...# ***## ..... ..... ..*.. #***# ..... ..... ..... *.#.. **... *.... ..... ..... ...
result:
ok good job!
Test #11:
score: 0
Wrong Answer
time: 3ms
memory: 134520kb
First Run Input
prepare 502 LO LI OZ LO IO ZT LO OZ OZ ZI IO OT ZO LZ IZ ZT TL TL LI IL IZ TO IO IL OL OL OL LO ZI OZ OZ ZO OZ IT OZ LZ TZ TO LZ TL ZL IZ LZ ZO ZL IO IL LI LT ZI OZ IZ OI TZ LI ZT IT LO TO ZI LT OT LZ OI LZ OZ LZ IT TO TI OI TO TO OI TZ ZL IO OZ ZO ZL LZ IZ OI TL TO TI LZ ZL ZL OZ TI ZI TL LO ZT LI ...
First Run Output
LIOLITLZOIOTZLZZLLLIITIILLLLIOZZZIZLTTZLLIZOLILILIOIITIZILTILTZILOLITIITTIZLOOOLLZILTIZLLZIILLTIIITOTTILLILTOOTLZILOLTLTLLZTOLLIIIIILIILIITOOZZTIOTTTLOTILTLTZLLOTZLZLOTTTTTOILZITZZLTTOZLLOTLZILZTILOTOOOIZTIZLZOOITOZTLTOZZLOTTLILZZLTZLZTOOIIITIOOZOOIZTLZTZLTOLZILLLOZIIITITTZZITTZIZOOOIIOOZOILTIIILZOO...
Second Run Input
play 502 L I O L I T L Z O I O T Z L Z Z L L L I I T I I L L L L I O Z Z Z I Z L T T Z L L I Z O L I L I L I O I I T I Z I L T I L T Z I L O L I T I I T T I Z L O O O L L Z I L T I Z L L Z I I L L T I I I T O T T I L L I L T O O T L Z I L O L T L T L L Z T O L L I I I I I L I I L I I T O O Z Z T I O
Second Run Output
***.. *.... ..... ..... ..... ###.. #.*.. ..*.. ..*.. ..*.. ##.** #..** ..... ..... ..... ##.## #..## ...*. ...*. ...** ##..# #*..# .*... .*... .*..# #.*.# #***# ..... ..... ....# #.#.# ...** ....* ....* ....# #*#.. **.#. *.... ..... ..... ###.. ##.#. #.... **... **... .##.. .#.#. .**** .#... .#... ...
result:
wrong answer wrong answer: invalid set [B] on step 146