QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#323453#4833. Tetra-puzzleduongnc0000 10ms9280kbC++206.5kb2024-02-09 21:30:202024-02-09 21:30:20

Judging History

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

  • [2024-02-09 21:30:20]
  • 评测
  • 测评结果:0
  • 用时:10ms
  • 内存:9280kb
  • [2024-02-09 21:30:20]
  • 提交

answer


#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")


#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

namespace Piece {
    vector<vector<pair<int, int>>> L = {{{0, 0}, {0, 1}, {1, 0}, {2, 0}},
                                        {{0, 0}, {0, 1}, {0, 2}, {1, 0}},
                                        {{0, 0}, {0, 1}, {1, 1}, {2, 1}},
                                        {{0, 0}, {0, 1}, {0, 2}, {1, 2}},
                                        {{0, 0}, {1, 0}, {2, 0}, {2, 1}},
                                        {{0, 0}, {1, 0}, {1, 1}, {1, 2}},
                                        {{2, 0}, {2, 1}, {1, 1}, {0, 1}},
                                        {{1, 0}, {1, 1}, {1, 2}, {0, 2}}};

    vector<vector<pair<int, int>>> I = {{{0, 0}, {0, 1}, {0, 2}, {0, 3}},
                                        {{0, 0}, {1, 0}, {2, 0}, {3, 0}}};

    vector<vector<pair<int, int>>> O = {{{0, 0}, {0, 1}, {1, 0}, {1, 1}}};

    vector<vector<pair<int, int>>> T = {{{0, 0}, {1, 0}, {1, 1}, {2, 0}},
                                        {{0, 0}, {0, 1}, {0, 2}, {1, 1}},
                                        {{0, 1}, {1, 0}, {1, 1}, {1, 2}},
                                        {{0, 1}, {1, 0}, {1, 1}, {2, 1}}};

    vector<vector<pair<int, int>>> Z = {{{0, 0}, {0, 1}, {1, 1}, {1, 2}},
                                        {{0, 1}, {1, 0}, {1, 1}, {2, 0}},
                                        {{0, 1}, {0, 2}, {1, 0}, {1, 1}},
                                        {{0, 0}, {1, 0}, {1, 1}, {2, 1}}};
    vector<vector<pair<int, int>>> get_vector(char shape) {
        if (shape == 'L') return L;
        if (shape == 'I') return I;
        if (shape == 'O') return O;
        if (shape == 'T') return T;
        if (shape == 'Z') return Z;
        return {};
    }
};

bool check(int x, int y) {
    return 0 <= x and x < 5 and 0 <= y and y < 5;
}

int conv(int x, int y) { return 24 - x * 5 - y; }

struct State {
    int a[5][5], msk, score;
    pair<int, char> prv;

    State() {
        memset(a, 0, sizeof a);
        score = 25, msk = 0, prv = {-1, 0};
    }

    bool operator < (const State &rhs) const {
        if (score == rhs.score) return msk < rhs.msk;
        return score < rhs.score;
    }

    void clear() {
        int row[5]{}, col[5]{};
        for (int i = 0; i < 5; ++i) for (int j = 0; j < 5; ++j) a[i][j] = !!a[i][j], row[i] += a[i][j], col[j] += a[i][j];
        for (int i = 0; i < 5; ++i) for (int j = 0; j < 5; ++j) if (row[i] == 5 or col[j] == 5) a[i][j] = 0, ++score, msk ^= 1 << conv(i, j);
    }

    pair<bool, pair<State, State>> test(int x, int y, vector<pair<int, int>> way, pair<int, char> cook) {
        State res = *this;
        for (auto [dx, dy] : way) {
            if (!check(x + dx, y + dy) or res.a[x + dx][y + dy]) return {false, {res, res}};
            res.a[x + dx][y + dy] = 2, --res.score, res.msk ^= 1 << conv(x + dx, y + dy);
        }
        pair<bool, pair<State, State>> rres = {true, {res, res}};
        res.clear(); res.prv = cook; rres.ss.ss = res;
        return rres;
    }
};

void try_piece(State cur, char shape, vector<State> &res, int idx) {
    auto ways = Piece::get_vector(shape);
    for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) for (int k = 0; k < isz(ways); ++k) {
        auto ncur = cur.test(i, j, ways[k], {idx, shape});
        if (ncur.ff) res.emplace_back(ncur.ss.ss);
    }
}

void try_piece2(State cur, char shape, vector<pair<State, State>> &res, int idx) {
    auto ways = Piece::get_vector(shape);
    for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) for (int k = 0; k < isz(ways); ++k) {
        auto ncur = cur.test(i, j, ways[k], {idx, shape});
        if (ncur.ff) res.emplace_back(ncur.ss.ss, ncur.ss.ff);
    }
}

void prepare() {
    int n; cin >> n;
    string res = "";
    vector<vector<State>> best(n + 1);
    best[0].resize(1);
    for (int i = 1; i <= n; ++i) {
        string s; cin >> s;
        for (int j = 0; j < isz(best[i - 1]); ++j) {
            try_piece(best[i - 1][j], s[0], best[i], j);
            try_piece(best[i - 1][j], s[1], best[i], j);
        }
        sort(rall(best[i]));
        if (isz(best[i]) > 100) best[i].resize(100);
    }
    int cidx = 0;
    for (int i = n; i >= 1; --i) {
        res.push_back(best[i][cidx].prv.ss);
        cidx = best[i][cidx].prv.ff;
    }
    reverse(all(res)); cout << res << endl;
}

void play() {
    int n; cin >> n;
    State cur;
    for (int i = 1; i <= n; ++i) {
        char ch; cin >> ch;
        vector<pair<State, State>> res;
        try_piece2(cur, ch, res, -1);
        assert(!res.empty());
        sort(rall(res)); cur = res[0].ss;
        // for (auto [x, y] : res) {
        //     cout << x.msk << " " << x.score << "\n";
        //     for (int j = 0; j < 5; ++j) {
        //         for (int k = 0; k < 5; ++k) {
        //             cout << x.a[j][k];
        //         }
        //         cout << "\n";
        //     }
        //     cout << "\n";
        // }
        for (int j = 0; j < 5; ++j) {
            for (int k = 0; k < 5; ++k) {
                if (cur.a[j][k] == 0) cout << '.';
                if (cur.a[j][k] == 1) cout << '#';
                if (cur.a[j][k] == 2) cout << '*';
            }
            cout << endl;
        }
        cur = res[0].ff;
        cout << endl;
    }
}

string name;

void solve() {
    cin >> name;
    if (name == "prepare") prepare();
    else play();
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 9280kb

First Run Input

prepare
6
TO LO ZI LI LT LT

First Run Output

TLIILL

Second Run Input

play
6
T
L
I
I
L
L

Second Run Output

***..
.*...
.....
.....
.....

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

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

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

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

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


result:

ok good job!

Test #2:

score: 100
Accepted
time: 0ms
memory: 3732kb

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: 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

LZZOOLZLZL

Second Run Input

play
10
L
Z
Z
O
O

Second Run Output

***..
*....
.....
.....
.....

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

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

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


result: