Submission #19050228

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint1000000007;
using III = tuple<int, int, int>;

void add_insert(map<III, mint> &dp, III &key1, III key2, set<III> &cur_set)
{
    dp[key2] += dp[key1];
    cur_set.insert(key2);
}

void update(map<III, mint> &dp, int A, set<III> &prev_set, set<III> &cur_set)
{
    for (auto key1 :  prev_set) {
        int j, k, l;
        tie(j, k, l) = key1;
        if (j == A)
            add_insert(dp, key1, {A + 1, k, l}, cur_set);
        if (k == A)
            add_insert(dp, key1, {j, A + 1, l}, cur_set);
        if (l == A)
            add_insert(dp, key1, {j, k, A + 1}, cur_set);
    }
}

int main()
{
    int N;
    cin >> N;
    vector<int> A_vec(N);
    for (int i = 0; i < N; ++i)
        cin >> A_vec.at(i);
    map<III, mint> dp;
    if (A_vec.at(0) != 0) {
        cout << 0 << endl;
        return 0;
    }
    III key1(1, 0, 0), key2(0, 1, 0), key3(0, 0, 1);
    dp[key1] = dp[key2] = dp[key3] = 1;
    set<III> prev_set, cur_set;
    prev_set.insert(key1);
    prev_set.insert(key2);
    prev_set.insert(key3);
    for (int i = 1; i < N; ++i) {
        int A = A_vec.at(i);
        update(dp, A, prev_set, cur_set);
        swap(prev_set, cur_set);
        cur_set.clear();
    }
    mint cnt(0);
    for (auto key : prev_set)
        cnt += dp[key];
    cout << cnt.val() << endl;
}

Submission Info

Submission Time
Task E - Colorful Hats 2
User atug
Language C++ (GCC 9.2.1)
Score 500
Code Size 1392 Byte
Status AC
Exec Time 253 ms
Memory 40996 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 34
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in59.txt, in61.txt, in62.txt, in63.txt, in64.txt, in65.txt, in66.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
in01.txt AC 6 ms 3616 KiB
in02.txt AC 31 ms 3456 KiB
in03.txt AC 2 ms 3408 KiB
in04.txt AC 6 ms 3952 KiB
in05.txt AC 231 ms 40820 KiB
in06.txt AC 232 ms 40760 KiB
in07.txt AC 231 ms 40848 KiB
in08.txt AC 229 ms 40996 KiB
in09.txt AC 2 ms 3404 KiB
in10.txt AC 38 ms 3700 KiB
in11.txt AC 5 ms 3588 KiB
in12.txt AC 2 ms 3536 KiB
in13.txt AC 113 ms 17464 KiB
in14.txt AC 119 ms 18140 KiB
in15.txt AC 184 ms 22436 KiB
in16.txt AC 253 ms 31688 KiB
in17.txt AC 230 ms 40888 KiB
in18.txt AC 18 ms 3624 KiB
in19.txt AC 2 ms 3484 KiB
in20.txt AC 3 ms 3648 KiB
in21.txt AC 27 ms 6660 KiB
in22.txt AC 176 ms 27736 KiB
in23.txt AC 174 ms 27796 KiB
in24.txt AC 172 ms 27628 KiB
in59.txt AC 2 ms 3588 KiB
in61.txt AC 2 ms 3564 KiB
in62.txt AC 2 ms 3512 KiB
in63.txt AC 2 ms 3540 KiB
in64.txt AC 5 ms 3456 KiB
in65.txt AC 2 ms 3612 KiB
in66.txt AC 2 ms 3588 KiB
sample_01.txt AC 2 ms 3588 KiB
sample_02.txt AC 2 ms 3512 KiB
sample_03.txt AC 3 ms 3440 KiB