QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#323453 | #4833. Tetra-puzzle | duongnc000 | 0 | 10ms | 9280kb | C++20 | 6.5kb | 2024-02-09 21:30:20 | 2024-02-09 21:30:20 |
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 {
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
}
詳細信息
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
***.. *.... ..... ..... ..... ###** #.**. ..... ..... ..... ..... #*##. **... *.... ..... ..... ####. ##**. #.**. .....