Submission #238524

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
238524	2020-06-11T15:54:52 Z	Sorting	Fishing Game (RMI19_fishing)	C++14	100 / 100	249 ms	173688 KB

fishing

#include <bits/stdc++.h>

using namespace std;

const long long k_Mod = 1e9 + 7;
const int k_N = 100 + 3;

typedef long long ll;

int n;
pair<int, bool> dp[3 * k_N][3 * k_N][3 * k_N][3][2];

long long get_answer(int ab, int ac, int bc, int stage, bool discarded){
    if(ab + ac + bc == 0)
        return 1;
    if(!stage){
        if(!discarded)
            return false;
        discarded = false;
    }

    //cout << ab << " " << ac << " " << bc << " " << stage << endl;

    auto &[answer, solved] = dp[ab][ac][bc][stage][discarded];
    if(solved)
        return answer;

    solved = true;
    answer = 0;

    if(stage == 0){
        if(ab + ac == 0)
            return answer = get_answer(ab, ac, bc, 1, discarded);

        if(ab)  answer += get_answer(ab - 1, ac, bc, 1, true) * (ll)ab % k_Mod;
        if(ac)  answer += get_answer(ab, ac - 1, bc + 1, 1, discarded) * (ll)ac % k_Mod;
        return answer %= k_Mod;
    }
    if(stage == 1){
        if(ab + bc == 0)
            return answer = get_answer(ab, ac, bc, 2, discarded);

        if(ab)  answer += get_answer(ab - 1, ac + 1, bc, 2, discarded) * (ll)ab % k_Mod;
        if(bc)  answer += get_answer(ab, ac, bc - 1, 2, true) * (ll)bc % k_Mod;
        return answer %= k_Mod;
    }
    if(stage == 2){
        if(ac + bc == 0)
            return answer = get_answer(ab, ac, bc, 0, discarded);

        if(ac)  answer += get_answer(ab, ac - 1, bc, 0, true) * (ll)ac % k_Mod;
        if(bc)  answer += get_answer(ab + 1, ac, bc - 1, 0, discarded) * (ll)bc % k_Mod;
        return answer %= k_Mod;
    }

    assert(false);
    return -1;
}

void solve_test(){
    static pair<int, int> pos[3 * k_N];

    for(int i = 1; i <= 3 * n; ++i)
        pos[i] = {-1, -1};

    int x;
    for(int i = 0; i < 2 * n; ++i){
        cin >> x;
        if(pos[x].first == -1)
            pos[x].first = 0;
        else
            pos[x].second = 0;
    }
    for(int i = 0; i < 2 * n; ++i){
        cin >> x;
        if(pos[x].first == -1)
            pos[x].first = 1;
        else
            pos[x].second = 1;
    }
    for(int i = 0; i < 2 * n; ++i){
        cin >> x;
        if(pos[x].first == -1)
            pos[x].first = 2;
        else
            pos[x].second = 2;
    }

    int ab = 0, ac = 0, bc = 0;
    for(int i = 1; i <= 3 * n; ++i){
        if(pos[i].first == pos[i].second)
            continue;

        //if(pos[i].first > pos[i].second)
        //    swap(pos[i].first, pos[i].second);

        if(pos[i].second == 1)
            ab++;
        else if(pos[i].first == 0)
            ac++;
        else
            bc++;
    }

    //cout << ab << " " << ac << " " << bc << endl;

    cout << get_answer(ab, ac, bc, 0, true) << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> n >> t;

    while(t--)
        solve_test();
}

Compilation message

fishing.cpp: In function 'long long int get_answer(int, int, int, int, bool)':
fishing.cpp:24:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     auto &[answer, solved] = dp[ab][ac][bc][stage][discarded];
           ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	512 KB	Output is correct
3	Correct	5 ms	1408 KB	Output is correct
4	Correct	9 ms	4736 KB	Output is correct
5	Correct	40 ms	33528 KB	Output is correct
6	Correct	63 ms	51320 KB	Output is correct
7	Correct	93 ms	74104 KB	Output is correct
8	Correct	129 ms	102392 KB	Output is correct
9	Correct	183 ms	136824 KB	Output is correct
10	Correct	249 ms	173688 KB	Output is correct