QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#323438#4833. Tetra-puzzleduongnc0000 8ms8016kbC++205.4kb2024-02-09 20:25:202024-02-09 20:25:20

Judging History

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

  • [2024-02-09 20:25:20]
  • 评测
  • 测评结果:0
  • 用时:8ms
  • 内存:8016kb
  • [2024-02-09 20:25: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;
}

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) 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, 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.a[x + dx][y + dy] = 1, --res.score;
        }
        res.clear();
        res.prv = cook;
        return {true, res};
    }
};

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

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<State> res;
        try_piece(cur, ch, res, -1);
        assert(!res.empty());
        sort(rall(res)); cur = res[0];
        for (int j = 0; j < 5; ++j) {
            for (int k = 0; k < 5; ++k) {
                cout << (cur.a[j][k] ? '*' : '.');
            }
            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

}

详细

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 8016kb

First Run Input

prepare
6
TO LO ZI LI LT LT

First Run Output

OLZITT

Second Run Input

play
6
O
L

Second Run Output

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

result:

wrong answer wrong answer: invalid set [A] on step 2