QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#323165#4833. Tetra-puzzlehotboy27030 0ms3884kbC++145.3kb2024-02-08 18:54:032024-02-08 18:54:03

Judging History

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

  • [2024-02-08 18:54:03]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3884kb
  • [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

详细

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

***..
*....
.....
.....
.....
###*.
#.**.
...*.
.....
.....
####.
#*##.
**.#.
*....
.....
####.
####.
##.#.
#**..
.**..
#*##.
#*##.
#**#.
#.#..
..#..
##.#.
##.#.
##.#.
#***.
.*...
#.*#.
#**#.
#*.#.
#.##.
.....
#.##.
####.
##.#.
#*##.
***..

result: