Submission #1173687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173687		InvMOD	PIN (CEOI10_pin)	C++20	100 / 100	358 ms	16172 KiB

pin

#include<bits/stdc++.h>

using namespace std;


void solve()
{
    int n,D; cin >> n >> D;

    vector<string> a(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    // dp[i]: pairs of substring that has same characters in >= i position

    vector<map<string, int>> counter((1 << 4)); vector<int> dp(5);
    for(int i = 1; i <= n; i++){
        for(int mask = 1; mask < (1 << 4); mask++){
            string tmp;
            for(int j = 0; j < 4; j++){
                if(mask >> j & 1){
                    tmp += a[i][j];
                }
            }

            dp[__builtin_popcount(mask)] += counter[mask][tmp];
            counter[mask][tmp] = counter[mask][tmp] + 1;
        }
    }

    D = 4 - D;
    /*
        dp[3] = dp[3] - 4C3 * dp[4]
        dp[2] = dp[2] - 3C2 * dp[3] + 4C2 * dp[4]
        dp[1] = dp[1] - 2C1 * dp[2] + 3C1 * dp[3] - 4C1 * dp[4]
        dp[0] = total_case - (dp[1] - dp[2] + dp[3] - dp[4])
    */

    if(D == 3) cout << dp[3] - 4 * dp[4] << "\n";
    if(D == 2) cout << dp[2] - 3 * dp[3] + 6 * dp[4] << "\n";
    if(D == 1) cout << dp[1] - 2 * dp[2] + 3 * dp[3] - 4 * dp[4] << "\n";
    if(D == 0) cout << 1ll * n * (n - 1) / 2 - (dp[1] - dp[2] + dp[3] - dp[4]) << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

pin.cpp: In function 'int32_t main()':
pin.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pin.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100