Submission #473933

#	Time	Username	Problem	Language	Result	Execution time	Memory
473933		model_code	L-triominoes (CEOI21_ltriominoes)	C++17	100 / 100	1728 ms	3712 KiB

ltrominoes

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
#include <cmath>
#include <string>

#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<
#define X first
#define Y second

using namespace std;

typedef pair<int, int> P;
typedef long long ll;

const int M = 13, MAX = 13;
int W, H;
int zero_one, one_zero;

void print_mask(int msk) {
  REP(i, W) {
    if (msk >> i & 1) printf("X");
    else printf(".");
  }
}

namespace brute {
  int brute_h;
  bool vis[M+2][MAX+1][1<<(MAX+1)];

  bool has(int msk, int pos) { return (msk >> pos) & 1; }

  void rek(int row, int col, int msk) {
    if (vis[row][col][msk]) return;
    vis[row][col][msk] = true;
    if (row == brute_h) return;

    if (col == W) {
      assert(!has(msk, W));
      rek(row+1, 0, msk);
      return;
    }

    if (msk & 1) rek(row, col+1, msk>>1);
    else {
      //up and up-left
      if (col && !has(msk, W) && !has(msk, W-1)) {
        int nmask = (msk | (1<<W) | (1<<(W-1))) >> 1;
        rek(row, col+1, nmask);
      }

      //up and up-right
      if (col != W-1 && !has(msk, W)) {
        int nmask = ((msk | (1<<W)) | (1<<(W+1))) >> 1;
        rek(row, col+1, nmask);
      }

      //right and up-right
      if (col != W-1 && !has(msk, 1)) {
        int nmask = (msk | (1<<(W+1)) | (1<<1)) >> 1;
        rek(row, col+1, nmask);
      }

      //up and right
      if (col != W-1 && !has(msk, W) && !has(msk, 1)) {
        int nmask = (msk | (1<<W) | (1<<1)) >> 1;
        rek(row, col+1, nmask);
      }
    }
  }

  vector <bool> reaches(const vector <bool> &V, int len) {
    assert(len >= 0 && len <= M);
    if (len == 0) return V;

    brute_h = len;
    memset(vis, 0, sizeof vis);

    REP(i, 1<<W)
      if (V[i])
        rek(0, 0, i);

    vector <bool> R((1<<W), false);
    REP(i, 1<<W)
      R[i] = vis[len][0][i];

    return R;
  }
}

vector <bool> reaches_single(int a, int len) {
  assert(len >= M);
  vector <bool> R(1<<W);

  if (W % 2 && a == zero_one) return R;

  if (W == 3) {
    int pc = __builtin_popcount(a);
    if (pc == 1) {
      R[zero_one] = true;
      if (len % 2) R[5 ^ a] = true;
      else R[a] = true;
    }
    else if (pc == 2) {
      if (a == one_zero) R[3] = R[6] = true;
      else if (len % 2) R[9-a] = true;
      else R[a] = true;
    }
    else {
      if (len % 2) R[7 ^ a] = true;
      else R[a] = true;
    }

    return R;
  }

  int pc = __builtin_popcount(a);
  len %= 3;
  REP(i, 1<<W)
    if (W % 2 == 0 || i != one_zero)
      R[i] = ((pc - len * W - __builtin_popcount(i)) % 3 == 0);

  return R;
}

vector <bool> reaches(const vector <bool> &V, int len) {
  if (len < M)
    return brute::reaches(V, len);

  vector <bool> R(1<<W);

  if (W <= 3) {
    REP(i, 1<<W)  {
      if (V[i]) {
        vector <bool> T = reaches_single(i, len);
        REP(j, 1<<W)
          R[j] = R[j] | T[j];
      }
    }
    return R;
  }

  bool has[3] = {false};
  REP(i, 1<<W) {
    if (V[i]) {
      if (i == zero_one && (W % 2)) continue;
      int pc = __builtin_popcount(i) % 3;
      if (has[pc]) continue;
      has[pc] = true;
      auto T = reaches_single(i, len);
      REP(j, 1<<W)
        R[j] = R[j] | T[j];
    }
  }

  return R;
}

vector <P> Mask_rows;
void load() {
  int k;
  scanf("%d%d%d", &W, &H, &k);
  vector <P> Tiles(k);

  REP(i, k) {
    int a, b;
    scanf("%d%d", &a, &b);
    Tiles[i] = P(b-1, a-1);
  }

  sort(Tiles.begin(), Tiles.end());

  for (int i=0; i<k; ) {
    int msk = 0, j = i;
    for (; j<k && Tiles[i].X == Tiles[j].X; j++)
      msk |= 1<<Tiles[j].Y;

    Mask_rows.push_back(P(Tiles[i].X, msk));
    i=j;
  }

  Mask_rows.push_back(P(H, (1<<W) - 1));
}

int main()
{
  load();

  REP(i, W) {
    if (i & 1) zero_one |= 1<<i;
    else one_zero |= 1<<i;
  }

  vector <bool> Curr_masks(1<<W, false);
  Curr_masks[0] = true;
  int prev=0;

  for (auto msk_row : Mask_rows) {
    int len = msk_row.X - prev;
    vector <bool> T = reaches(Curr_masks, len);
    vector <bool> Nxt(1<<W, false);

    REP(i, 1<<W)
      if (T[i] && !(i & msk_row.Y))
        Nxt[i | msk_row.Y] = true;

    Curr_masks = Nxt;
    prev = msk_row.X;
  }

  if (Curr_masks[(1<<W)-1]) printf("YES\n");
  else printf("NO\n");

  return 0;
}

Compilation message (stderr)

ltrominoes.cpp: In function 'void load()':
ltrominoes.cpp:168:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |   scanf("%d%d%d", &W, &H, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ltrominoes.cpp:173:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |     scanf("%d%d", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 7 / 7
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20