QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#295430 | #4833. Tetra-puzzle | ucup-team087# | 0 | 0ms | 0kb | C++14 | 4.9kb | 2023-12-31 06:20:17 | 2023-12-31 06:20:17 |
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
const string ILOTZ = "ILOTZ";
constexpr int L = 25;
constexpr int BEAM = 100;
constexpr int BINGOS[10] = {
31 << 0, 31 << 5, 31 << 10, 31 << 15, 31 << 20,
1082401 << 0, 1082401 << 1, 1082401 << 2, 1082401 << 3, 1082401 << 4,
};
vector<vector<int>> MINOSS;
void init() {
constexpr int DAT[5][9][4] = {
{{0,1,2,3}, {0,5,10,15}, {-1,-1,-1,-1}},
{{0,5,10,11}, {2,5,6,7}, {0,1,6,11}, {0,1,2,5}, {1,6,10,11}, {0,1,2,7}, {0,1,5,10}, {0,5,6,7}, {-1,-1,-1,-1}},
{{0,1,5,6}, {-1,-1,-1,-1}},
{{0,1,2,6}, {0,5,6,10}, {1,5,6,7}, {1,5,6,11}, {-1,-1,-1,-1}},
{{0,1,6,7}, {1,5,6,10}, {1,2,5,6}, {0,5,6,11}, {-1,-1,-1,-1}},
};
MINOSS.assign(5, {});
for (int a = 0; a < 5; ++a) {
for (int i = 0; ~DAT[a][i][0]; ++i) {
int base = 0;
int maxX = 0, maxY = 0;
for (int j = 0; j < 4; ++j) {
const int z = DAT[a][i][j];
base |= 1 << z;
chmax(maxX, z / 5);
chmax(maxY, z % 5);
}
for (int dx = 0; maxX + dx < 5; ++dx) for (int dy = 0; maxY + dy < 5; ++dy) {
MINOSS[a].push_back(base << (dx * 5 + dy));
}
}
// cerr<<ILOTZ[a]<<": "<<MINOSS[a].size()<<endl;
}
}
int move(int p, int a, int b) {
const int mino = MINOSS[a][b];
if (p & mino) {
return -1;
}
p |= mino;
int q = 0;
for (int i = 0; i < 10; ++i) {
if (!(~p & BINGOS[i])) {
q |= BINGOS[i];
}
}
p -= q;
return p;
}
constexpr int INF = 1001001001;
mt19937_64 rng(58);
int eval(int p) {
return rng() % INF;
}
struct State {
int score;
int p;
int prv;
int a, b;
};
State select(int p, int a) {
State sm{-INF, -1, -1, -1, -1};
for (int b = 0; b < (int)MINOSS[a].size(); ++b) {
const int pp = move(p, a, b);
if (~pp) {
const State s{eval(pp), pp, -1, a, b};
if (sm.score < s.score) {
sm = s;
}
}
}
return sm;
}
int main() {
init();
char typ[110];
scanf("%s", typ);
if (!strcmp(typ, "prepare")) {
int N;
scanf("%d", &N);
char A[1010][3];
for (int i = 0; i < N; ++i) {
scanf("%s", A[i]);
}
vector<vector<State>> dp(N + 1);
dp[0].push_back(State{0, 0, -1, -1, -1});
for (int i = 0; i < N; ++i) {
for (int x = 0; x < (int)dp[i].size(); ++x) {
const int p = dp[i][x].p;
for (int j = 0; j < 2; ++j) {
const int a = ILOTZ.find(A[i][j]);
State sm = select(p, a);
sm.prv = x;
if (~sm.p) {
dp[i + 1].push_back(sm);
}
}
sort(dp[i + 1].begin(), dp[i + 1].end(), [&](const State &s0, const State &s1) -> bool {
return (s0.score > s1.score);
});
if ((int)dp[i + 1].size() > BEAM) {
dp[i + 1].resize(BEAM);
}
}
cerr<<"|dp["<<i+1<<"]| = "<<dp[i+1].size()<<endl;
}
string ans(N, '?');
for (int i = N, x = 0; i; ) {
const State s = dp[i][x];
--i;
ans[i] = ILOTZ[s.a];
x = s.prv;
}
puts(ans.c_str());
} else if (!strcmp(typ, "play")) {
int N;
scanf("%d", &N);
int p = 0;
for (int i = 0; i < N; ++i) {
char c;
scanf(" %c", &c);
const int a = ILOTZ.find(c);
const State s = select(p, a);
for (int x = 0; x < 5; ++x) {
for (int y = 0; y < 5; ++y) {
const int z = x * 5 + y;
putchar((p >> z & 1) ? '#' : (MINOSS[s.a][s.b] >> z & 1) ? '*' : '.');
}
puts("");
}
fflush(stdout);
p = s.p;
}
} else {
assert(false);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Stage 2: Program answer Runtime Error
First Run Input
prepare 6 TO LO ZI LI LT LT
First Run Output
TOIITL
Second Run Input
play 6 T O I I T
Second Run Output
..... ...*. ..*** ..... ..... ..... ...#. ..### .**.. .**.. .**** ...#. ..### .##.. .##.. .#### *..#. *.### *##.. *##..