SRM706_div2_Hard.cpp

#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using namespace std;
typedef long long int lli;
lli MOD = 1000000007;
class MappingABC2
{
public:
    int countStrings(vector<int> t)
    {
        int n = t.size();
        lli ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    map<int, set<int>> v;
                    set<int> p;
                    if (t[j] == t[i])
                        continue;
                    if (t[i] == t[k])
                        continue;
                    if (t[j] == t[k])
                        continue;
                    rep(l, n)
                    {
                        if (l < i) {
                            v[t[l]].insert(0);
                        } else if (i < l && l < j) {
                            v[t[l]].insert(1);
                        } else if (j < l && l < k) {
                            v[t[l]].insert(2);
                        } else if (k < l) {
                            // v[t[l]].insert(3);
                        }
                        p.insert(t[l]);
                    }
                    if (v[t[i]].find(0) != v[t[i]].end()) {
                        continue;
                    }
                    if (v[t[j]].find(1) != v[t[j]].end()) {
                        continue;
                    }
                    if (v[t[k]].find(2) != v[t[k]].end()) {
                        continue;
                    }
                    lli temp = 1;
                    for (auto l : p) {
                        auto s = v[l];
                        if (l == t[i] || l == t[j] || l == t[k])
                            continue;
                        if (s.size() == 3) {
                            temp = 0;
                            break;
                        } else if (s.size() == 2) {
                            continue;
                        } else if (s.size() == 1) {
                            temp = (temp * 2) % MOD;
                        } else if (s.size() == 0) {
                            temp = (temp * 3) % MOD;
                        }
                    }
                    // if (temp > 0) {
                    //     cout << temp << ' ' << i << ' ' << j << ' ' << k << endl;
                    // }
                    ans = (ans + temp + MOD) % MOD;
                }
            }
        }
        return ans;
    }

    // BEGIN CUT HERE
public:
    void run_test(int Case)
    {
        if ((Case == -1) || (Case == 0))
            test_case_0();
        if ((Case == -1) || (Case == 1))
            test_case_1();
        if ((Case == -1) || (Case == 2))
            test_case_2();
        if ((Case == -1) || (Case == 3))
            test_case_3();
        if ((Case == -1) || (Case == 4))
            test_case_4();
    }

private:
    template <typename T>
    string print_array(const vector<T>& V)
    {
        ostringstream os;
        os << "{ ";
        for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter)
            os << '\"' << *iter << "\",";
        os << " }";
        return os.str();
    }
    void verify_case(int Case, const int& Expected, const int& Received)
    {
        cerr << "Test Case #" << Case << "...";
        if (Expected == Received)
            cerr << "PASSED" << endl;
        else {
            cerr << "FAILED" << endl;
            cerr << "\tExpected: \"" << Expected << '\"' << endl;
            cerr << "\tReceived: \"" << Received << '\"' << endl;
        }
    }
    void test_case_0()
    {
        int Arr0[] = {9, 9, 2, 9, 4};
        vector<int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
        int Arg1 = 2;
        verify_case(0, Arg1, countStrings(Arg0));
    }
    void test_case_1()
    {
        int Arr0[] = {3, 2, 1};
        vector<int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
        int Arg1 = 1;
        verify_case(1, Arg1, countStrings(Arg0));
    }
    void test_case_2()
    {
        int Arr0[] = {1, 2, 2, 1, 2, 1, 2};
        vector<int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
        int Arg1 = 0;
        verify_case(2, Arg1, countStrings(Arg0));
    }
    void test_case_3()
    {
        int Arr0[] = {7, 50, 1, 50, 1, 50, 1, 10, 7};
        vector<int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
        int Arg1 = 20;
        verify_case(3, Arg1, countStrings(Arg0));
    }
    void test_case_4()
    {
        int Arr0[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48};
        vector<int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
        int Arg1 = 166952139;
        verify_case(4, Arg1, countStrings(Arg0));
    }

    // END CUT HERE
};
// BEGIN CUT HERE
int main()
{
    MappingABC2 ___test;
    ___test.run_test(-1);
}
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor