QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#323165 | #4833. Tetra-puzzle | hotboy2703 | 0 | 0ms | 3884kb | C++14 | 5.3kb | 2024-02-08 18:54:03 | 2024-02-08 18:54:03 |
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1LL)
string best_move = "TLZOI";
pll piece[][4]={
{{0,0},{1,0},{-1,0},{0,-1}},
{{0,0},{0,1},{0,2},{1,0}},
{{0,0},{0,1},{-1,1},{1,0}},
{{0,0},{0,1},{1,0},{1,1}},
{{0,0},{0,1},{0,2},{0,3}},
};
ll penalty[5][5];
void cv_to_board(ll state,ll board[5][5]){
ll ptr = 0;
for (ll i = 0;i < 5;i ++){
for (ll j = 0;j < 5;j ++,ptr++){
board[i][j] = BIT(state,ptr);
}
}
}
ll to_state(ll board[5][5]){
ll res = 0;
ll ptr = 0;
for (ll i = 0;i < 5;i ++){
for (ll j = 0;j < 5;j ++,ptr++){
res ^= board[i][j]*MASK(ptr);
}
}
return res;
}
ll evaluate(ll state){
ll board[5][5];
ll res = 0;
cv_to_board(state,board);
for (ll i = 0;i < 5;i ++){
for (ll j = 0;j < 5;j ++){
res += penalty[i][j] * board[i][j];
}
}
return res;
}
void print_move(ll cur_state,ll nxt_state){
ll ptr = 0;
for (ll i = 0;i < 5;i ++){
for (ll j = 0;j < 5;j ++,ptr++){
if (BIT(nxt_state,ptr)){
if (BIT(cur_state,ptr)){
cout<<'#';
}
else{
cout<<'*';
}
}
else{
cout<<'.';
}
}
cout<<endl;
}
}
void print_state(ll state){
ll board[5][5];
cv_to_board(state,board);
for (ll i = 0;i < 5;i ++){
for (ll j = 0;j < 5;j ++){
cout<<board[i][j];
}
cout<<endl;
}
}
ll f_clear(ll state){
ll board[5][5];
cv_to_board(state,board);
ll row[5]={},col[5]={};
for (ll i = 0;i < 5;i ++)col[i] = row[i] = 1;
for (ll i = 0;i < 5;i ++){
for (ll j = 0;j < 5;j ++){
col[j] &= board[i][j];
row[i] &= board[i][j];
}
}
for (ll i = 0;i < 5;i ++){
for (ll j = 0;j < 5;j ++){
if (col[j] || row[i])board[i][j] = 0;
}
}
return to_state(board);
}
vector <pll> all_move(ll state,ll type){
ll board[5][5];
vector <pll> ans_move;
cv_to_board(state,board);
auto valid = [&](pll pnt){
if (pnt.fi >= 0 && pnt.fi<5 && pnt.se >= 0 && pnt.se<5 && board[pnt.fi][pnt.se]==0)return 1;
else return 0;
};
for (ll flip = 0;flip <= 1;flip++){
for (ll rot = 0;rot < 4;rot++){
vector <pll> cur_piece;
for (ll i = 0;i < 4;i ++){
pll cur = piece[type][i];
if (flip){
cur.fi = -cur.fi;
}
for (ll j = 0;j < rot;j ++){
ll x = cur.fi,y = cur.se;
cur.fi = y;
cur.se = -x;
}
cur_piece.push_back(cur);
}
for (ll i = 0;i < 5;i ++){
for (ll j = 0;j < 5;j ++){
bool ok = 1;
for (ll k = 0;k < 4;k ++){
pll cur = cur_piece[k];
ok &= valid({cur.fi+i,cur.se+j});
}
if (ok){
for (ll k = 0;k < 4;k ++){
pll cur = cur_piece[k];
board[cur.fi+i][cur.se+j] = 1;
}
ll nxt_state = to_state(board);
ll end_state = f_clear(nxt_state);
ans_move.push_back({nxt_state,end_state});
for (ll k = 0;k < 4;k ++){
pll cur = cur_piece[k];
board[cur.fi+i][cur.se+j] = 0;
}
}
}
}
}
}
return ans_move;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
string task;
cin>>task;
if (task == "prepare"){
ll n;
cin>>n;
for (ll i= 1;i <= n; i++){
string s;
cin>>s;
for (auto x:best_move){
if (x==s[0]||x==s[1]){
cout<<x;
break;
}
}
}
}
else{
ll n;
cin>>n;
ll cur_state = 0;
while (n--){
char x;
cin>>x;
ll type;
for (ll i = 0;i < 5;i ++){
if (x==best_move[i]){
type = i;
break;
}
}
vector <pll> choices = all_move(cur_state,type);
ll ans_eval = 1e9;
pll ans = {-1,-1};
for (auto x:choices){
ll val = evaluate(x.se);
if (val < ans_eval){
ans = x;
ans_eval = val;
}
}
assert(ans.fi!=-1);
// cout<<cur_state<<' '<<ans.fi<<' '<<ans.se<<'\n';
print_move(cur_state,ans.fi);
cur_state = ans.se;
// print_state(cur_state);
}
}
}
// 7 10 3 9 8 9 10 11
//TLZLTT
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3884kb
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: 0ms
memory: 3600kb
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
Stage 2: Program answer Runtime Error
First Run Input
prepare 10 LO TZ ZO OI OL ZL ZO TL OZ LO
First Run Output
LTZOLLZTZL
Second Run Input
play 10 L T Z O L L Z T Z
Second Run Output
***.. *.... ..... ..... ..... ###*. #.**. ...*. ..... ..... ####. #*##. **.#. *.... ..... ####. ####. ##.#. #**.. .**.. #*##. #*##. #**#. #.#.. ..#.. ##.#. ##.#. ##.#. #***. .*... #.*#. #**#. #*.#. #.##. ..... #.##. ####. ##.#. #*##. ***..