【C++】AtCoderの問題がREになる原因が分からない

前提・実現したいこと

AtCoder Beginner Contest 050 C Lining Upという問題を解いているのですが、どうしてもREになる原因が分からず困っております。何かわかる方は助言いただけますと幸いです。

発生している問題・エラーメッセージ

提出した内容はこちらになります。subtask_1_min_valid_01.txt というケースでのみREが発生し、他のケースでは問題ないようです。該当ケースを見るとメモリが259272 KBとなっており、メモリ制限の256MBを超えているのも気になります。しかしその場合はMLEという別のステータスになるそうなので、やはり原因は別のところにあるのではないかと考えています。

該当のソースコード

コメントは後から付け足したものです。

C++
1#pragma GCC target("avx2")
2#pragma GCC optimize("O3")
3#pragma GCC optimize("unroll-loops")
4
5#include <algorithm>
6#include <iostream>
7#include <map>
8#include <unordered_map>
9
10using namespace std;
11typedef long long ll;
12
13const ll MOD = 1E+09 + 7;
14
15const int MAX_N = 100000;
16
17ll N;
18
19// x^ a をMODで割った余りを求める関数
20ll modPow(ll x, ll a);
21
22int main()
23{
24    ios::sync_with_stdio(false);
25    cin.tie(nullptr);
26
27    cin >> N;
28
29    unordered_map<ll, int> mp; //キーが左右の人数の差の絶対値、それに対応する値は出現数
30
31    for (int i = 0; i < N; i++) {
32        ll a;
33        cin >> a;
34        if (mp.count(a)) { //mpにすでに値があれば出現数を1つ増やします
35            mp[a]++;
36        } else { //なければ新しく作ります
37            mp.insert(make_pair(a, 1));
38        }
39    }
40
41    bool isPossible = true;
42
43    ll j = !(N & 1); //Nが偶数の場合は1、奇数の場合は1からスタート
44
45    for (; j <= N - 1; j += 2) { //左右の人数の差の絶対値の取りえる値は0 or 1 ~ N - 1 まで
46        if (mp.count(j)) {
47            if (mp[j] != 2 && !(j == 0 && mp[j] == 1)) { //真ん中の場合を除き出現数が2でないときはこの並び方は不可能
48                isPossible = false;
49                break;
50            }
51        } else { //どこかの数が出てこない場合も不可能
52            isPossible = false;
53            break;
54        }
55    }
56
57    ll ans;
58
59    if (isPossible) {
60        ans = modPow(2, N / 2);
61    } else {
62        ans = 0;
63    }
64
65    cout << ans << "\n";
66
67    return 0;
68}
69
70ll modPow(ll x, ll a)
71{
72    if (a == 1)
73        return x % MOD;
74    if (a % 2 == 0) {
75        ll t = modPow(x, a / 2);
76        return (t * t) % MOD;
77    } else {
78        return ((x % MOD) * modPow(x, a - 1)) % MOD;
79    }
80}
81

試したこと

modPowという関数についてですが、この部分は別の機会で作ったものでこれまでも正しく動作していたので恐らく問題はないと思います。またこのmodPowとは別のアルゴリズムでべき乗計算を行うコードを提出しても同じケースでREとなりましたので、やはりmain関数内のどこかに原因があるのではないかと思っています。
割り算の分母は全て定数なのでゼロ除算はないと思います。

行動規範の内容に同意します

回答1件

ベストアンサー

REになっているケースの入力を入れてデバッガで追えば一発です。

Nが1でans = modPow(2, N / 2);を呼んでしまっているため、

C++
1    if (a % 2 == 0) {
2        ll t = modPow(x, a / 2);
3        return (t * t) % MOD;
4    }

でmodPow(2, 0)を無限に呼び続けています。

modPowという関数についてですが、この部分は別の機会で作ったものでこれまでも正しく動作していたので恐らく問題はないと思います。またこのmodPowとは別のアルゴリズムでべき乗計算を行うコードを提出しても同じケースでREとなりましたので

以前私が回答で貼ったmodPowに差し替えて実行すると正解の1が返りますが、これでもだめですか？(提出しての確認はしていません)

C++
1ll modPow(ll x, ll a)
2{
3    long long ret = 1;
4    x %= MOD;
5    while (0 < a)
6    {
7        if (a % 2 == 0) {
8            x = (x * x) % MOD;
9            a /= 2;
10        }
11        else {
12            ret = (ret * x) % MOD;
13            --a;
14        }
15    }
16    return ret;
17}