Submission #434038


Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

struct Ans {
	int o, x;
};

Ans m1[3*3*3*3*3*3*3*3*3][2];
bool m2[3*3*3*3*3*3*3*3*3][2] = {0};

const int O = 0, X = 1;

int b[2][3], c[3][2];

int pow3[11];

int setValue(int board, int x, int y, int v) {
	return board + (v * pow3[3*y+x]);
}
int getValue(int board, int x, int y) {
	return board % pow3[3*y+x+1] / pow3[3*y+x];
}
int rank(int o, int x) {
	return o < 0 || x < 0 ? -1 : o > x ? 2 : o == x ? 1 : 0;
}
bool comp(int o1, int x1, int o2, int x2) {
	int r1 = rank(o1, x1), r2 = rank(o2, x2);
	if (r1 != r2) return r1 > r2;
	else {
		if (o1 > o2) return true;
		if (o1 == o2 && x1 < x2) return true;
		else return false;
	}
	return false;
}

Ans min_max(int board, int turn) {
	if (m2[board][turn]) return m1[board][turn];

	bool f = true;
	for (int y = 0; y < 3; ++y) {
		for (int x = 0; x < 3; ++x) {
			if (getValue(board, x, y) == 0) f = false;
		}
	}

	Ans ret = (Ans){-1, -1};
	if (f) {
		ret.o = ret.x = 0;
		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < 3; ++j) {
				if (getValue(board, i, j) == getValue(board, i+1, j)) {
					ret.o += b[i][j];
				}
				else {
					ret.x += b[i][j];
				}
			}
		}
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 2; ++j) {
				if (getValue(board, i, j) == getValue(board, i, j+1)) {
					ret.o += c[i][j];
				}
				else {
					ret.x += c[i][j];
				}
			}
		}
	}
	else {
		for (int y = 0; y < 3; ++y) {
			for (int x = 0; x < 3; ++x) {
				if (getValue(board, x, y) == 0) {
					Ans a = min_max(setValue(board, x, y, turn+1), (int)!turn);
					if (turn == 0 && comp(a.o, a.x, ret.o, ret.x)) {
//					if (turn == 0 && a.o > ret.o) {
						ret = a;
					}
					else if (turn == 1 && comp(a.x, a.o, ret.x, ret.o)) {
//					else if (turn == 1 && a.x > ret.x) {
						ret = a;
					}
				}
			}
		}
	}
	return m2[board][turn] = true, m1[board][turn] = ret;
}

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];

	for (int i = 0, k = 1; i < 11; ++i, k *= 3) {
		pow3[i] = k;
	}
	Ans ans = min_max(0, O);
	cout << ans.o << " " << ans.x << endl;
}

Submission Info

Submission Time
Task C - 双子と○×ゲーム
User dragonex
Language C++ (GCC 4.9.2)
Score 0
Code Size 2280 Byte
Status WA
Exec Time 33 ms
Memory 1264 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
WA × 2
WA × 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 WA 33 ms 1264 KB
sample-02.txt WA 27 ms 1180 KB
test-01.txt WA 31 ms 1056 KB
test-02.txt WA 30 ms 1172 KB
test-03.txt WA 29 ms 1176 KB
test-04.txt WA 29 ms 1052 KB
test-05.txt WA 28 ms 1120 KB
test-06.txt WA 29 ms 1056 KB
test-07.txt WA 27 ms 1064 KB
test-08.txt WA 29 ms 1188 KB
test-09.txt WA 29 ms 1060 KB
test-10.txt WA 32 ms 1180 KB
test-11.txt WA 29 ms 1056 KB
test-12.txt WA 29 ms 1172 KB
test-13.txt WA 29 ms 1136 KB
test-14.txt WA 30 ms 1184 KB
test-15.txt WA 29 ms 1180 KB
test-16.txt WA 29 ms 1068 KB
test-17.txt WA 28 ms 1052 KB
test-18.txt WA 30 ms 1056 KB
test-19.txt WA 28 ms 1184 KB
test-20.txt WA 29 ms 1056 KB