QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#323173#4833. Tetra-puzzlehotboy27030 0ms3652kbC++145.7kb2024-02-08 19:03:522024-02-08 19:03:53

Judging History

你现在查看的是最新测评结果

  • [2024-02-08 19:03:53]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3652kb
  • [2024-02-08 19:03:52]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

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

First Run Output


Second Run Input


Second Run Output


result: