QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#323173 | #4833. Tetra-puzzle | hotboy2703 | 0 | 0ms | 3652kb | C++14 | 5.7kb | 2024-02-08 19:03:52 | 2024-02-08 19:03:53 |
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;
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];swap(ans0,ans1);cur_state=ans1.se;}
if (evaluate(ans0.se)==INF)assert(0);
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
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
First Run Input
prepare 6 TO LO ZI LI LT LT
First Run Output
TLZLLL
Second Run Input
play 6 T L Z L L L
Second Run Output
.*... **... .*... ..... ..... .#*** ##*.. .#... ..... ..... .#### ###*. .#**. ..*.. ..... .#### ####. .###. ..#*. .***. .#..# ##*** .#*.. ..... .#... .#..# ***.. *##.. ..... .#...
result:
ok good job!
Test #2:
score: 100
Accepted
time: 0ms
memory: 3620kb
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 1: Program answer Runtime Error
First Run Input
prepare 10 LO TZ ZO OI OL ZL ZO TL OZ LO