test/aoj/0401.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 10:56:39+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0401

Depends on

• 不偏ゲーム (grundy数) (src/Game/ImpartialGame.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0401
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/Game/ImpartialGame.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using Game= pair<int, int>;
 auto f= [&](const Game &g) {
  vector<Game> ret;
  if (g.first > 0) ret.emplace_back(g), ret.back().first--;
  for (int i= min(g.first, g.second); i > 0; i--) ret.emplace_back(g), ret.back().second-= i;
  if (g.second > 0) ret.emplace_back(g), ret.back().first++, ret.back().second--;
  return ret;
 };
 ImpartialGame<Game, decltype(f)> ig(f);
 int sum= 0, N;
 cin >> N;
 while (N--) {
  int w, b;
  cin >> w >> b;
  sum^= ig.eval(Game(w, b));
 }
 cout << !sum << '\n';
 return 0;
}

#line 1 "test/aoj/0401.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0401
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 2 "src/Game/ImpartialGame.hpp"
#include <map>
#include <algorithm>
#line 5 "src/Game/ImpartialGame.hpp"
template <typename Game, typename F> struct ImpartialGame {
 std::map<Game, unsigned> mp;
 F f;  // : Game -> std::vector<Game>
 static unsigned mex(std::vector<unsigned> S) {
  std::sort(S.begin(), S.end()), S.erase(std::unique(S.begin(), S.end()), S.end());
  for (unsigned i= 0; i < S.size(); i++)
   if (S[i] != i) return i;
  return S.size();
 }
public:
 ImpartialGame(const F &_f): f(_f) {}
 unsigned eval(Game g) {
  if (mp.count(g)) return mp[g];
  std::vector<unsigned> S;
  for (const auto &_g: f(g)) S.emplace_back(eval(_g));
  return mp[g]= mex(S);
 }
};
#line 7 "test/aoj/0401.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using Game= pair<int, int>;
 auto f= [&](const Game &g) {
  vector<Game> ret;
  if (g.first > 0) ret.emplace_back(g), ret.back().first--;
  for (int i= min(g.first, g.second); i > 0; i--) ret.emplace_back(g), ret.back().second-= i;
  if (g.second > 0) ret.emplace_back(g), ret.back().first++, ret.back().second--;
  return ret;
 };
 ImpartialGame<Game, decltype(f)> ig(f);
 int sum= 0, N;
 cin >> N;
 while (N--) {
  int w, b;
  cin >> w >> b;
  sum^= ig.eval(Game(w, b));
 }
 cout << !sum << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_01.in	AC	47 ms	4 MB
g++-13	00_sample_02.in	AC	15 ms	4 MB
g++-13	10_lose_small_001.in	AC	16 ms	4 MB
g++-13	10_lose_small_002.in	AC	45 ms	5 MB
g++-13	10_lose_small_003.in	AC	27 ms	4 MB
g++-13	10_lose_small_004.in	AC	41 ms	4 MB
g++-13	10_lose_small_005.in	AC	30 ms	4 MB
g++-13	10_lose_small_006.in	AC	7 ms	4 MB
g++-13	15_win_small_001.in	AC	12 ms	4 MB
g++-13	15_win_small_002.in	AC	40 ms	4 MB
g++-13	15_win_small_003.in	AC	25 ms	4 MB
g++-13	15_win_small_004.in	AC	41 ms	4 MB
g++-13	15_win_small_005.in	AC	39 ms	4 MB
g++-13	15_win_small_006.in	AC	58 ms	5 MB
g++-13	20_lose_medium_001.in	AC	70 ms	5 MB
g++-13	20_lose_medium_002.in	AC	70 ms	5 MB
g++-13	20_lose_medium_003.in	AC	69 ms	5 MB
g++-13	20_lose_medium_004.in	AC	68 ms	5 MB
g++-13	20_lose_medium_005.in	AC	62 ms	5 MB
g++-13	20_lose_medium_006.in	AC	71 ms	5 MB
g++-13	25_win_medium_001.in	AC	70 ms	5 MB
g++-13	25_win_medium_002.in	AC	68 ms	5 MB
g++-13	25_win_medium_003.in	AC	68 ms	5 MB
g++-13	25_win_medium_004.in	AC	68 ms	5 MB
g++-13	25_win_medium_005.in	AC	68 ms	5 MB
g++-13	25_win_medium_006.in	AC	71 ms	5 MB
g++-13	30_lose_large_001.in	AC	72 ms	5 MB
g++-13	30_lose_large_002.in	AC	72 ms	5 MB
g++-13	30_lose_large_003.in	AC	72 ms	5 MB
g++-13	30_lose_large_004.in	AC	72 ms	5 MB
g++-13	30_lose_large_005.in	AC	73 ms	5 MB
g++-13	30_lose_large_006.in	AC	73 ms	5 MB
g++-13	35_win_large_001.in	AC	71 ms	5 MB
g++-13	35_win_large_002.in	AC	71 ms	5 MB
g++-13	35_win_large_003.in	AC	71 ms	5 MB
g++-13	35_win_large_004.in	AC	71 ms	5 MB
g++-13	35_win_large_005.in	AC	71 ms	5 MB
g++-13	35_win_large_006.in	AC	71 ms	5 MB
g++-13	40_max_001.in	AC	72 ms	5 MB
g++-13	40_max_002.in	AC	73 ms	5 MB
g++-13	50_min_001.in	AC	5 ms	4 MB
g++-13	50_min_002.in	AC	71 ms	5 MB
clang++-18	00_sample_01.in	AC	46 ms	5 MB
clang++-18	00_sample_02.in	AC	15 ms	4 MB
clang++-18	10_lose_small_001.in	AC	15 ms	4 MB
clang++-18	10_lose_small_002.in	AC	45 ms	5 MB
clang++-18	10_lose_small_003.in	AC	27 ms	4 MB
clang++-18	10_lose_small_004.in	AC	41 ms	4 MB
clang++-18	10_lose_small_005.in	AC	31 ms	4 MB
clang++-18	10_lose_small_006.in	AC	7 ms	4 MB
clang++-18	15_win_small_001.in	AC	12 ms	4 MB
clang++-18	15_win_small_002.in	AC	39 ms	4 MB
clang++-18	15_win_small_003.in	AC	25 ms	4 MB
clang++-18	15_win_small_004.in	AC	40 ms	4 MB
clang++-18	15_win_small_005.in	AC	38 ms	4 MB
clang++-18	15_win_small_006.in	AC	57 ms	5 MB
clang++-18	20_lose_medium_001.in	AC	68 ms	5 MB
clang++-18	20_lose_medium_002.in	AC	68 ms	5 MB
clang++-18	20_lose_medium_003.in	AC	67 ms	5 MB
clang++-18	20_lose_medium_004.in	AC	66 ms	5 MB
clang++-18	20_lose_medium_005.in	AC	61 ms	5 MB
clang++-18	20_lose_medium_006.in	AC	70 ms	5 MB
clang++-18	25_win_medium_001.in	AC	69 ms	5 MB
clang++-18	25_win_medium_002.in	AC	66 ms	5 MB
clang++-18	25_win_medium_003.in	AC	66 ms	5 MB
clang++-18	25_win_medium_004.in	AC	66 ms	5 MB
clang++-18	25_win_medium_005.in	AC	66 ms	5 MB
clang++-18	25_win_medium_006.in	AC	69 ms	5 MB
clang++-18	30_lose_large_001.in	AC	69 ms	5 MB
clang++-18	30_lose_large_002.in	AC	69 ms	5 MB
clang++-18	30_lose_large_003.in	AC	71 ms	5 MB
clang++-18	30_lose_large_004.in	AC	70 ms	5 MB
clang++-18	30_lose_large_005.in	AC	72 ms	5 MB
clang++-18	30_lose_large_006.in	AC	71 ms	5 MB
clang++-18	35_win_large_001.in	AC	70 ms	5 MB
clang++-18	35_win_large_002.in	AC	70 ms	5 MB
clang++-18	35_win_large_003.in	AC	71 ms	5 MB
clang++-18	35_win_large_004.in	AC	70 ms	5 MB
clang++-18	35_win_large_005.in	AC	70 ms	5 MB
clang++-18	35_win_large_006.in	AC	69 ms	5 MB
clang++-18	40_max_001.in	AC	71 ms	5 MB
clang++-18	40_max_002.in	AC	71 ms	5 MB
clang++-18	50_min_001.in	AC	4 ms	4 MB
clang++-18	50_min_002.in	AC	70 ms	5 MB

Back to top page