Submission #432830


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int INF = 1<<28;
int b[5][5], c[5][5];
map<vector<string>, pair<int, int> > mem;

pair<int, int> calc(const vector<string> &g) {
  pair<int, int> res(0, 0);
  for(int i = 0; i < 2; ++i) {
    for(int j = 0; j < 3; ++j) {
      if(g[i][j] == g[i+1][j]) res.first += b[i][j];
      else res.second += b[i][j];
    }
  }
  for(int i = 0; i < 3; ++i) {
    for(int j = 0; j < 2; ++j) {
      if(g[i][j] == g[i][j+1]) res.first += c[i][j];
      else res.second += c[i][j];
    }
  }
  return res;
}

pair<int, int> rec(vector<string> g, int t, int k) {
  if(mem.count(g)) return mem[g];
  if(k == 9) {
    return mem[g] = calc(g);
  }
  pair<int, int> res(-INF, -INF);

  for(int i = 0; i < 3; ++i) {
    for(int j = 0; j < 3; ++j) {
      if(g[i][j] != '.') continue;
      if(t == 0) g[i][j] = 'o';
      else g[i][j] = 'x';
      pair<int, int> p = rec(g, 1-t, k+1);
      g[i][j] = '.';
      if(t == 0) {
        if(p.first > res.first) res = p;
      } else {
        if(p.second > res.second) res = p;
      }
    }
  }
  return mem[g] = res;
}

int main() {
  for(int i = 0; i < 2; ++i) {
    for(int j = 0; j < 3; ++j) {
      cin >> b[i][j];
    }
  }
  for(int i = 0; i < 3; ++i) {
    for(int j = 0; j < 2; ++j) {
      cin >> c[i][j];
    }
  }
  pair<int, int> p = rec(vector<string>(3, string(3, '.')), 0, 0);
  cout << p.first << endl;
  cout << p.second << endl;
  return 0;
}

Submission Info

Submission Time
Task C - 双子と○×ゲーム
User zukky
Language C++ (GCC 4.9.2)
Score 100
Code Size 1507 Byte
Status AC
Exec Time 74 ms
Memory 2272 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 22
Set Name Test Cases
Sample sample-01.txt, sample-02.txt
All test-01.txt, test-02.txt, test-03.txt, test-04.txt, test-05.txt, test-06.txt, test-07.txt, test-08.txt, test-09.txt, test-10.txt, test-11.txt, test-12.txt, test-13.txt, test-14.txt, test-15.txt, test-16.txt, test-17.txt, test-18.txt, test-19.txt, test-20.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
sample-01.txt AC 72 ms 2208 KB
sample-02.txt AC 72 ms 2208 KB
test-01.txt AC 70 ms 2272 KB
test-02.txt AC 73 ms 2212 KB
test-03.txt AC 74 ms 2208 KB
test-04.txt AC 72 ms 2212 KB
test-05.txt AC 72 ms 2220 KB
test-06.txt AC 70 ms 2196 KB
test-07.txt AC 71 ms 2204 KB
test-08.txt AC 72 ms 2204 KB
test-09.txt AC 71 ms 2208 KB
test-10.txt AC 70 ms 2212 KB
test-11.txt AC 70 ms 2216 KB
test-12.txt AC 67 ms 2212 KB
test-13.txt AC 69 ms 2208 KB
test-14.txt AC 70 ms 2268 KB
test-15.txt AC 71 ms 2208 KB
test-16.txt AC 71 ms 2208 KB
test-17.txt AC 69 ms 2212 KB
test-18.txt AC 69 ms 2212 KB
test-19.txt AC 69 ms 2204 KB
test-20.txt AC 70 ms 2208 KB