QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#295430#4833. Tetra-puzzleucup-team087#0 0ms0kbC++144.9kb2023-12-31 06:20:172023-12-31 06:20:17

Judging History

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

  • [2023-12-31 06:20:17]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [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

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

result: