QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#323446#4833. Tetra-puzzleduongnc0000 10ms8408kbC++206.8kb2024-02-09 21:10:042024-02-09 21:10:05

Judging History

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

  • [2024-02-09 21:10:05]
  • 评测
  • 测评结果:0
  • 用时:10ms
  • 内存:8408kb
  • [2024-02-09 21:10:04]
  • 提交

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;
}

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

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

    bool operator < (const State &rhs) const {
        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;
    }

    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;
        }
        pair<bool, pair<State, State>> rres = {true, {res, res}};
        res.clear(); res.prv = cook; rres.ss.ss = res;
        return rres;
    }

    int msk() {
        int res = 0;
        for (int i = 0; i < 5; ++i) for (int j = 0; j < 5; ++j) res = res << 1 | a[i][j];
        return res;
    }

    // int count_way(vector<pair<int, int>> &way) {
    //     int res = 0;
    //     for (int x = 0; x < 4; ++x) for (int y = 0; y < 4; ++y) {
    //         int cnt = 1;
    //         for (auto [dx, dy] : way) res &= (check(x + dx, y + dy) and !a[x + dx][y + dy]);
    //         res += cnt;
    //     }
    //     return res;
    // }

    // int count_ways() {
    //     for (auto ch : ['L', 'I', 'O', 'T', 'Z']) {
    //         for (auto way : Piece::get_vector(ch))
    //     }
    // }
};

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), [&](pair<State, State> A, pair<State, State> B) {
            if (A.ff.score == B.ff.score) return A.ff.msk() < B.ff.msk();
            return A.ff.score < B.ff.score;
        }); cur = res[0].ss;
        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;
    }
}

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

}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 7960kb

First Run Input

prepare
6
TO LO ZI LI LT LT

First Run Output

OLZITT

Second Run Input

play
6
O
L
Z
I
T
T

Second Run Output

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

result:

ok good job!

Test #2:

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

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: 100
Accepted
time: 10ms
memory: 8408kb

First Run Input

prepare
10
LO TZ ZO OI OL ZL ZO TL OZ LO

First Run Output

LTOILLZLZL

Second Run Input

play
10
L
T
O
I
L
L
Z
L
Z
L

Second Run Output

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

result:

ok good job!

Test #4:

score: 0
Stage 2: Program answer Runtime Error

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

TOLLZLILIZTLILLZIZOLLLTIIZILL

Second Run Input

play
29
T
O
L
L
Z
L
I
L
I
Z

Second Run Output

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

result: