题解 | GCPC总决赛

#include <iostream>
#include <vector>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
using ll = long long;

vector<int> a, b;
map<pair<int, int>, ll> memo[3];  // memo[0]:win, memo[1]:lose, memo[2]:draw

ll dfs(int mask, int diff) {
    int cnt = __builtin_popcount(mask);
    if (cnt == a.size()) {
        if (diff > 0) return 1;  // win
        else if (diff < 0) return 2;  // lose
        else return 3;  // draw
    }
    
    ll res = 0;
    for (int j = 0; j < b.size(); j++) {
        if (mask >> j & 1) continue;
        
        int new_diff = diff;
        if (a[cnt] > b[j]) new_diff++;
        else if (a[cnt] < b[j]) new_diff--;
        
        res += dfs(mask | (1 << j), new_diff);
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    a.resize(n); b.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    
    // 这里用暴力验证
    vector<int> p(n);
    for (int i = 0; i < n; i++) p[i] = i;
    
    ll win = 0, lose = 0, draw = 0;
    do {
        int dark = 0, yxl = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] > b[p[i]]) dark++;
            else if (a[i] < b[p[i]]) yxl++;
        }
        if (dark > yxl) win++;
        else if (dark < yxl) lose++;
        else draw++;
    } while (next_permutation(p.begin(), p.end()));
    
    cout << win << " " << lose << " " << draw << endl;
    return 0;
}