QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#323466#4833. Tetra-puzzleduongnc0000 74ms31820kbC++206.3kb2024-02-09 21:44:142024-02-09 21:44:15

Judging History

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

  • [2024-02-09 21:44:15]
  • 评测
  • 测评结果:0
  • 用时:74ms
  • 内存:31820kb
  • [2024-02-09 21:44:14]
  • 提交

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[5][5] = {{0, 1, 2, 3, 4},
                  {5, 9, 10, 11, 12},
                  {6, 13, 16, 17, 18},
                  {7, 14, 19, 21, 22},
                  {8, 15, 20, 23, 24}};

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(all(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(all(res)); 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;
        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: 9ms
memory: 9608kb

First Run Input

prepare
6
TO LO ZI LI LT LT

First Run Output

OLILLL

Second Run Input

play
6
O
L
I
L
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: 100
Accepted
time: 12ms
memory: 9640kb

First Run Input

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

First Run Output

LZZIOLOLOL

Second Run Input

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

Second Run Output

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

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

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

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

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

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

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

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

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

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

result:

ok good job!

Test #4:

score: 100
Accepted
time: 43ms
memory: 24980kb

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

TTZLILILIZTLILLZIIOLLLTOIZILL

Second Run Input

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

Second Run Output

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

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

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

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

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

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

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

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

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

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

result:

ok good job!

Test #5:

score: 100
Accepted
time: 53ms
memory: 31820kb

First Run Input

prepare
36
TI ZT IT IT OT OZ IL TZ ZO LO LZ ZL OT ZI IL OT OT ZI ZT TZ TI LT LO OL IL OL IZ OZ OL ZL LT IO ZO ZL ZO LT

First Run Output

ITTIOOLZOLLLOILTTIZTILOLILIOLLLIZLOL

Second Run Input

play
36
I
T
T
I
O
O
L
Z
O
L
L
L
O
I
L
T
T
I
Z
T
I
L
O
L
I
L
I
O
L
L
L
I
Z
L
O
L

Second Run Output

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

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

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

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

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

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

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

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

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

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

result:

ok good job!

Test #6:

score: 100
Accepted
time: 74ms
memory: 31040kb

First Run Input

prepare
57
LT OI TL IZ OT TL LT TI LO LT LO LO OL IO LI IT TZ TZ IO ZT TI OT OI TL TL ZT TZ OL OI LI OZ ZI TO LZ IO IO LT OZ TO OZ IZ TZ LT ZO TO TZ OT LT ZO OL IL LO ZT OZ OL IL ZI

First Run Output

LITIOLLTOLLLLILITZITIOILLZZLILZITLIOLZTZZTTZTTTTOLIOZOLII

Second Run Input

play
57
L
I
T
I
O
L
L
T
O
L
L
L
L
I
L
I
T
Z
I
T
I
O
I
L
L
Z
Z
L
I
L
Z
I
T
L
I
O
L
Z
T
Z
Z
T
T
Z
T
T
T
T
O
L
I
O
Z
O
L
I
I

Second Run Output

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

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

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

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

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

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

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

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

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

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

result:

ok good job!

Test #7:

score: 0
Stage 2: Program answer Runtime Error

First Run Input

prepare
88
ZL OL OT IT LO ZL OI ZT TO OI OL OL LZ ZT TL TZ IO ZL TZ TO IL LO ZT OL LT ZI TZ IL LT ZL OT TI ZO ZO ZT OZ TL TL LO OI TO OZ LI ZO ZT ZT IO IZ OZ ZO ZI ZO IO IO TI OL IL IT IL TL TL ZL IT IT ZO IO OL IL ZI TO OL IL ZI LZ LT IL LI ZO IL TL IT LI ZI OL TO OZ IZ OZ

First Run Output

LLTIOLIZTILLLZTTILTOIOTLLITITLTIOZTZLLLIOZLZTTIIZZIZOITLIILLTZIIZILLIOLIILLIIZLLIIILTZIZ

Second Run Input

play
88
L
L
T
I
O
L
I
Z
T
I
L
L
L
Z
T
T
I
L
T
O
I

Second Run Output

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

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

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

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

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

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

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

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

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

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

result: