QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#323438 | #4833. Tetra-puzzle | duongnc000 | 0 | 8ms | 8016kb | C++20 | 5.4kb | 2024-02-09 20:25:20 | 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