QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#323448 | #4833. Tetra-puzzle | duongnc000 | 0 | 40ms | 22068kb | C++20 | 6.2kb | 2024-02-09 21:15:39 | 2024-02-09 21:15:39 |
Judging History
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 {
return tie(score, msk) < tie(rhs.score, rhs.msk);
}
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, 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 (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: 12ms
memory: 7964kb
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: 1ms
memory: 3616kb
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: 13ms
memory: 7944kb
First Run Input
prepare 10 LO TZ ZO OI OL ZL ZO TL OZ LO
First Run Output
OTZILLZTZL
Second Run Input
play 10 O T Z I L L Z T Z L
Second Run Output
.**.. .**.. ..... ..... ..... .##.. .##.. ..*.. ..**. ..*.. .#**. .#.** ..... ...#. ..... .###. .#*## ..*.. ..*#. ..*.. .#.#. .#.## .**.. .*.#. .*... ..*#. ***## ..#.. ...#. ..... **##. .**.. ..#.. ...#. ..... ####. .##.. ..#.. ..*#. .***. ##*#. .#**. ...*. ...#. .#.#. ###.. .##.. ..**. ..*...
result:
ok good job!
Test #4:
score: 100
Accepted
time: 40ms
memory: 22068kb
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
TOLLILILITZLZTLTIITLLLTIIZILL
Second Run Input
play 29 T O L L I L I L I T Z L Z T L T I I T L L L T I I Z I L L
Second Run Output
***.. .*... ..... ..... ..... ###** .#.** ..... ..... ..... ***.. *#.## ..... ..... ..... ###.. ##.## .*... .*... .**.. #.#.. #..## ****. ..... ..#.. #.#.. #..## ####* ..*** ..#.. #.#.. #..## .**** ..### ..#.. #.#.. #..## *#### *.### **#.. .*#.. .*.## .*... .*### .##.. .*#.. ***## ..... ..#...
result:
ok good job!
Test #5:
score: 0
Stage 2: Program answer Runtime Error
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
TZIITZIZOOLZTZIOTITTILLLILZZLZLOZLZL
Second Run Input
play 36 T Z I I T Z I Z O O L Z T Z I O T I T T I L L L I L Z Z L Z L O
Second Run Output
***.. .*... ..... ..... ..... ###** .#**. ..... ..... ..... *.... *###. *.... *.... ..... #.... ####. #.... #**** ..... #.... ####* #..** ....* ..... #.... ..*.. #**## .*..# ..... #**** ..#.. ..... .#..# ..... .**.. **#.. ..... .#..# ..... .##.. ###** ...** .#..# ..... .##** ...** ...## .#....