QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#323177 | #4833. Tetra-puzzle | hotboy2703 | 0 | 1ms | 3900kb | C++14 | 6.1kb | 2024-02-08 19:12:33 | 2024-02-08 19:12:35 |
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";
const ll INF = 1e9;
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){
if (state<0)return INF;
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;
}
pll greedy(ll cur_state,ll type){
vector <pll> choices = all_move(cur_state,type);
ll ans_eval = INF;
pll ans = {-1,-1};
for (auto x:choices){
ll val = evaluate(x.se);
if (val < ans_eval){
ans = x;
ans_eval = val;
}
}
return ans;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
string task;
cin>>task;
ll ptr = 0;
for (ll i = 0;i < 5;i ++){
for (ll j = 0;j < 5;j ++,ptr++){
ll dist_i = min(abs(i-0),abs(i-4));
ll dist_j = min(abs(j-0),abs(j-4));
penalty[i][j] = MASK(dist_i+dist_j);
// cout<<penalty[i][j]<<' ';
}
// cout<<endl;
}
if (task == "prepare"){
ll n;
cin>>n;
ll cur_state = 0;
for (ll i= 1;i <= n; i++){
string s;
cin>>s;
ll type[2];
for (ll j = 0;j < 2;j ++){
for (ll k = 0;k < sz(best_move);k ++){
if (best_move[k] == s[j]){type[j] = k;break;}
}
}
pll ans0 = greedy(cur_state,type[0]);
pll ans1 = greedy(cur_state,type[1]);
char choose = s[0];
cur_state = ans0.se;
if (evaluate(ans0.se)>evaluate(ans1.se)){choose = s[1];cur_state=ans1.se;}
if (evaluate(cur_state)==INF)assert(0);
// cout<<evaluate(cur_state)<<endl;
// print_state(cur_state);
cout<<choose;
}
}
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;
}
}
pll ans=greedy(cur_state,type);
print_move(cur_state,ans.fi);
cur_state = ans.se;
// print_state(cur_state);
}
}
}
// 7 10 3 9 8 9 10 11
//TLZLLL
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3600kb
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: 3628kb
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: 1ms
memory: 3900kb
First Run Input
prepare 10 LO TZ ZO OI OL ZL ZO TL OZ LO
First Run Output
LTOILZOLOL
Second Run Input
play 10 L T O I L Z O L O L
Second Run Output
***.. *.... ..... ..... ..... ###.. #.... *.... **... *.... .##** ...** ..... .#... ..... .#### ..*## ..*.. .#*.. ..*.. .#.## ...## ...*. .#.*. ...** .#..# ....# ....* .#.** ...*# .#.** ...** ..... .#.#. ...#. .#.## ...## ...** .#.#* ...#* .#.** ...** ..... .#... ..... .#.## ...## ...*. .#.*. ...**
result:
ok good job!
Test #4:
score: 100
Accepted
time: 1ms
memory: 3672kb
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
TTLLILZLITTOZLLTIIOLTLTIIOILL
Second Run Input
play 29 T T L L I L Z L I T T O Z L L T I I O L T L T I I O I L L
Second Run Output
....* ...** ....* ..... ..... .*..# ***## ....# ..... ..... .#..# ..... ....# ....* ..*** .#..# ..... *...# *...# **### .#..# .*... #*..# #*..# .*... ....# ..... #***# #*..# ..... ....# ..... ..... ##**# ...** ....# ..... ..... *.... ***## ....# ..... ..... #**** ..... ....# ..... ....* ...** ....* ...
result:
ok good job!
Test #5:
score: 100
Accepted
time: 1ms
memory: 3660kb
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
ITITOOLZZLLLTIITOZTTILLOILIOLZLIOLZT
Second Run Input
play 36 I T I T O O L Z Z L L L T I I T O Z T T I L L O I L I O L Z L I O L Z T
Second Run Output
****. ..... ..... ..... ..... ####* ...** ....* ..... ..... ..... ...## ****# ..... ..... .*... ***## ..... ..... ..... .#.** ...** ..... ..... ..... .#.## ...## ..... **... **... .#.## ...## ...*. ##.*. ##.** *#..# **..# .*... ##... ##..# #...# #...# ....* #..** #..*# #..** #..*. ...*. #..#. #..#. ...
result:
ok good job!
Test #6:
score: 100
Accepted
time: 1ms
memory: 3592kb
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
LILITLLILLLLLOIITTITTTILLZTLIIOITLIOTOTOITLZTZOLOLILTOOII
Second Run Input
play 57 L I L I T L L I L L L L L O I I T T I T T T I L L Z T L I I O I T L I O T O T O I T L Z T Z O L O L I L T O O I I
Second Run Output
***.. *.... ..... ..... ..... ###.. #.*.. ..*.. ..*.. ..*.. ##... #.... *.... *.... **... *#... *.... *.... *.... .#... ##*** #..*. #.... #.... .#... ...** #..#* #...* #.... .#... ...## #..## #..*# #..*. .#.** ....# #...# #...# #**** .#..# ...** #...* #...* ..... .#... ...## #...# #***# .*... .#... ...
result:
ok good job!
Test #7:
score: 0
Stage 1: Program answer Runtime Error
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