GCJ2019 Round1C

a.cpp

#include <stdio.h>
#include <string.h>

int main() {
  unsigned char hand_by_name[256];
  hand_by_name['R'] = 0;
  hand_by_name['P'] = 1;
  hand_by_name['S'] = 2;

  int T; scanf("%d", &T);
  for(int tci = 0; tci < T; ++tci) {
    int A; scanf("%d", &A);
    int opponent_hands_len[255];
    static char opponent_hands[255][501];
    bool opponent_alive[255];
    for(int i = 0; i < A; ++i) {
      scanf(" %500s", opponent_hands[i]);
      opponent_hands_len[i] = strlen(opponent_hands[i]);
      for(int j = 0; j < opponent_hands_len[i]; ++j) {
        opponent_hands[i][j] = hand_by_name[(int)opponent_hands[i][j]];
      }
      opponent_alive[i] = true;
    }

    char my_hands[501];
    int my_hands_len = 0;
    bool alive = true;
    for(int j = 0;; ++j) {
      bool hand_possible[3] = {false, false, false};
      for(int i = 0; i < A; ++i) {
        if(!opponent_alive[i]) continue;
        int hand = opponent_hands[i][j % opponent_hands_len[i]];
        hand_possible[hand] = true;
      }
      int variety = (int)hand_possible[0] + (int)hand_possible[1] + (int)hand_possible[2];
      // fprintf(stderr, "round %d: variety = %d (%d, %d, %d)\n", j, variety, hand_possible[0], hand_possible[1], hand_possible[2]);
      if(variety == 3) {
        alive = false;
        break;
      } else if(variety == 1) {
        int my_hand = hand_possible[0] ? 1 : hand_possible[1] ? 2 : 0;
        my_hands[my_hands_len++] = my_hand;
        break;
      }
      // variety == 2
      int hand_to_miss = hand_possible[0] ? hand_possible[1] ? 1 : 0 : 2;
      my_hands[my_hands_len++] = hand_to_miss;
      for(int i = 0; i < A; ++i) {
        if(!opponent_alive[i]) continue;
        int hand = opponent_hands[i][j % opponent_hands_len[i]];
        opponent_alive[i] = hand == hand_to_miss;
      }
      // number of alive opponents must decrease, but won't be <= 0 here
    }
    if(alive) {
      for(int j = 0; j < my_hands_len; ++j) {
        my_hands[j] = "RPS"[(int)my_hands[j]];
      }
      my_hands[my_hands_len] = '\0';
      printf("Case #%d: %s\n", tci + 1, my_hands);
    } else {
      printf("Case #%d: IMPOSSIBLE\n", tci + 1);
    }
  }
}

b.cpp

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

int F;

char ask(int x);

const int COUNTS[] = {23, 5, 1, 0};
void solve(char result[]) {
  bool alive[119];
  for(int i = 0; i < 119; ++i) alive[i] = true;
  for(int round = 0; round < 4; ++round) {
    char column[119];
    int counts[5] = {0, 0, 0, 0, 0};
    for(int old_round = 0; old_round < round; ++old_round) {
      // adjust count
      counts[result[old_round] - 'A'] = -1;
    }
    for(int i = 0; i < 119; ++i) {
      if(!alive[i]) continue;
      column[i] = ask(i * 5 + round + 1);
      counts[column[i] - 'A']++;
    }
    int al = std::find(counts, counts+5, COUNTS[round]) - counts;
    result[round] = 'A' + al;
    for(int i = 0; i < 119; ++i) {
      if(!alive[i]) continue;
      alive[i] = column[i] - 'A' == al;
    }
  }
  result[4] = 'A' ^ 'B' ^ 'C' ^ 'D' ^ 'E' ^ result[0] ^ result[1] ^ result[2] ^ result[3];
}

char ask(int x) {
  printf("%d\n", x);
  fflush(stdout);

  char ch;
  scanf(" %c", &ch);
  if(ch == 'N') exit(0);
  return ch;
}

int main() {
  int T; scanf("%d%d", &T, &F);
  for(int tci = 0; tci < T; ++tci) {
    char result[6];
    solve(result);

    result[5] = '\0';
    printf("%s\n", result);
    fflush(stdout);

    char ch;
    scanf(" %c", &ch);
    if(ch == 'N') exit(0);
  }
}

c.cpp

#include <stdio.h>
#include <algorithm>

int main() {
  int T; scanf("%d", &T);
  for(int tci = 0; tci < T; ++tci) {
    int R, C; scanf("%d%d", &R, &C);
    char board[15][16];
    unsigned int board_vbits[15] = {};
    unsigned int board_hbits[15] = {};
    for(int y = 0; y < R; ++y) {
      scanf(" %15s", board[y]);
      for(int x = 0; x < C; ++x) {
        if(board[y][x] == '#') {
          board_vbits[x] |= (1 << y);
          board_hbits[y] |= (1 << x);
        }
      }
    }

    int subgame_grundy[16][16][16][16];
    for(int sy = R; sy >= 0; --sy) {
      for(int sx = C; sx >= 0; --sx) {
        for(int ey = sy; ey <= R; ++ey) {
          for(int ex = sx; ex <= C; ++ex) {
            if(sy == ey || sx == ex) {
              subgame_grundy[sy][sx][ey][ex] = 0;
              continue;
            }
            int op_grundies[15];
            int op_grundies_len = 0;
            int hmask = (1 << ex) - (1 << sx);
            int vmask = (1 << ey) - (1 << sy);
            for(int iy = sy; iy < ey; ++iy) {
              if(board_hbits[iy] & hmask) continue;
              int op_grundy = subgame_grundy[sy][sx][iy][ex] ^ subgame_grundy[iy+1][sx][ey][ex];
              op_grundies[op_grundies_len++] = op_grundy;
            }
            for(int ix = sx; ix < ex; ++ix) {
              if(board_vbits[ix] & vmask) continue;
              int op_grundy = subgame_grundy[sy][sx][ey][ix] ^ subgame_grundy[sy][ix+1][ey][ex];
              op_grundies[op_grundies_len++] = op_grundy;
            }

            std::sort(op_grundies, op_grundies + op_grundies_len);
            op_grundies_len = std::unique(op_grundies, op_grundies + op_grundies_len) - op_grundies;
            int grundy = 0;
            for(; grundy < op_grundies_len && op_grundies[grundy] == grundy; ++grundy);
            subgame_grundy[sy][sx][ey][ex] = grundy;
            // fprintf(stderr, "subgame_grundy[%d][%d][%d][%d] = %d\n", sy, sx, ey, ex, grundy);
          }
        }
      }
    }
    int winning_opening_count = 0;
    {
      int sy = 0, ey = R, sx = 0, ex = C;
      int hmask = (1 << ex) - (1 << sx);
      int vmask = (1 << ey) - (1 << sy);
      for(int iy = sy; iy < ey; ++iy) {
        if(board_hbits[iy] & hmask) continue;
        int op_grundy = subgame_grundy[sy][sx][iy][ex] ^ subgame_grundy[iy+1][sx][ey][ex];
        if(op_grundy == 0) winning_opening_count += ex - sx;
      }
      for(int ix = sx; ix < ex; ++ix) {
        if(board_vbits[ix] & vmask) continue;
        int op_grundy = subgame_grundy[sy][sx][ey][ix] ^ subgame_grundy[sy][ix+1][ey][ex];
        if(op_grundy == 0) winning_opening_count += ey - sy;
      }
    }
    printf("Case #%d: %d\n", tci + 1, winning_opening_count);
  }
}

Makefile

#!/usr/bin/make -f

EXECS = a b c
CXX = g++
CXXFLAGS = -O2 -Wall -Wextra -g -std=gnu++14

all: $(EXECS)

clean:
	$(RM) $(EXECS)