Submission #479924

#	Time	Username	Problem	Language	Result	Execution time	Memory
479924		Ozy	Amusement Park (CEOI19_amusementpark)	C++17	42 / 100	3053 ms	161996 KiB

amusementpark

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 18
#define mod 998244353

lli n,m,total;
lli pot[47],orden[MAX+2];
pair<lli,lli> slides[47];
unordered_map<lli, lli> mapa;

void checa() {

    lli num = 0;
    lli rparcial = 0;

    rep(i,1,m) {
        if (orden[slides[i].first] > orden[slides[i].second]) {
            num += pot[i];
            rparcial++;
        }
    }

    if (mapa.find(num) == mapa.end()) {
        mapa[num] = 1;
        total += rparcial;
        if (total >= mod) total -= mod;
    }

}

void genera(lli k) {
    rep(i,1,n) {
        if (orden[i] > 0) continue;

        orden[i] = k;
        if (k == n) checa();
        else genera(k+1);
        orden[i] = 0;
    }
}

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

    cin >> n >> m;
    rep(i,1,m) cin >> slides[i].first >> slides[i].second;

    pot[1] = 1;
    rep(i,2,m) pot[i] = pot[i-1]*2;

    genera(1);

    cout << total;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37