結果
問題 | No.334 門松ゲーム |
ユーザー | haruteru |
提出日時 | 2016-01-28 15:37:58 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 2,863 bytes |
コンパイル時間 | 887 ms |
コンパイル使用メモリ | 68,912 KB |
実行使用メモリ | 4,348 KB |
最終ジャッジ日時 | 2023-10-21 16:31:31 |
合計ジャッジ時間 | 1,786 ms |
ジャッジサーバーID (参考情報) |
judge9 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 1 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 2 ms
4,348 KB |
testcase_08 | AC | 2 ms
4,348 KB |
testcase_09 | AC | 2 ms
4,348 KB |
testcase_10 | AC | 2 ms
4,348 KB |
testcase_11 | AC | 1 ms
4,348 KB |
testcase_12 | AC | 9 ms
4,348 KB |
testcase_13 | AC | 2 ms
4,348 KB |
testcase_14 | AC | 2 ms
4,348 KB |
testcase_15 | AC | 6 ms
4,348 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <limits.h> struct Answer { int n1, n2, n3, level; }; std::vector<Answer> ans; int player_e(std::vector<int> &k, int level); int player_d(std::vector<int> &k, int level); int check(int a, int b, int c) { if (a > b && a < c) return 1; if (a > c && a < b) return 1; if (c > b && c < a) return 1; if (c > a && c < b) return 1; return 0; } int player_e(std::vector<int> &k, int level) { int lv = level; for (int n1 = 0; n1 < k.size(); n1++) { for (int n2 = n1 + 1; n2 < k.size(); n2++) { for (int n3 = n2 + 1; n3 < k.size(); n3++) { if (check(k[n1], k[n2], k[n3]) != 0) { std::vector<int> t = k; t.erase(t.begin() + n3); t.erase(t.begin() + n2); t.erase(t.begin() + n1); if (t.size() == 0) { return -1; // win } int rc = player_d(t, level+1); if (rc == -1) { return -1; // win } if (lv < rc) { lv = rc; } } } } } return lv; } int player_d(std::vector<int> &k, int level) { int lv = INT_MAX; int detect = 0; for (int n1 = 0; n1 < k.size(); n1++) { for (int n2 = n1 + 1; n2 < k.size(); n2++) { for (int n3 = n2 + 1; n3 < k.size(); n3++) { if (check(k[n1], k[n2], k[n3]) != 0) { std::vector<int> t = k; t.erase(t.begin() + n3); t.erase(t.begin() + n2); t.erase(t.begin() + n1); int rc = player_e(t, level+1); if (rc < 0) { continue; } if (lv < rc) { lv = rc; } detect = 1; if (level == 0) { Answer a = { n1, n2, n3, rc, }; ans.push_back(a); } } } } } if (detect == 0) { return -1; } return lv; } int main() { int N; std::vector<int> k; std::cin >> N; k.resize(N); for (int n = 0; n < N; n++) { std::cin >> k[n]; } player_d(k, 0); if (ans.size() > 0) { Answer &a = ans[0]; for (int n = 1; n < ans.size(); n++) { if (a.level > ans[n].level) { a = ans[n]; } } std::cout << a.n1 << " "; std::cout << a.n2 << " "; std::cout << a.n3 << std::endl; } else { std::cout << -1 << std::endl; } return 0; }