Submission #142836

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
142836	2019-08-11T12:01:28 Z	popovicirobert	PIN (CEOI10_pin)	C++14	100 / 100	247 ms	5860 KB

pin

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long


/*const int MOD = 998244353;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}

inline int inv(int x) {
    return lgput(x, MOD - 2);
}*/

/*int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/

using namespace std;

vector <string> str;
int n;
bool mark[5];

ll solve(int step, int last) {
    if(step == 0) {
        vector <string> all;
        for(int i = 0; i < n; i++) {
            string cur;
            for(int j = 0; j < 4; j++) {
                if(mark[j] == 0)
                    cur.push_back(str[i][j]);
            }
            all.push_back(cur);
        }
        sort(all.begin(), all.end());
        ll ans = 0;
        int i = 0;
        while(i < n) {
            int j = i;
            while(j < n && all[i] == all[j]) {
                j++;
            }
            ans += 1LL * (j - i - 1) * (j - i) / 2;
            i = j;
        }
        return ans;
    }
    else {
        if(last == 3) return 0;
        ll ans = 0;
        for(int i = last + 1; i < 4; i++) {
            mark[i] = 1;
            ans += solve(step - 1, i);
            mark[i] = 0;
        }
        return ans;
    }
}

int comb[10][10];

inline void prec() {
    int i, j;
    for(i = 0; i < 10; i++) {
        comb[i][0] = 1;
        for(j = 1; j <= i; j++) {
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        }
    }
}

int main() {
#ifdef HOME
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, j, d;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> d;
    str.resize(n);
    for(auto &it : str) {
        cin >> it;
    }

    prec();

    vector <ll> ways(5);
    for(i = 0; i <= 4; i++) {
        ways[i] = solve(i, -1);
        for(j = i - 1; j >= 0; j--) {
            ways[i] -= ways[j] * comb[4 - j][4 - i];
        }
    }
    cout << ways[d];

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	504 KB	Output is correct
2	Correct	8 ms	504 KB	Output is correct
3	Correct	7 ms	504 KB	Output is correct
4	Correct	92 ms	2796 KB	Output is correct
5	Correct	113 ms	3184 KB	Output is correct
6	Correct	112 ms	3124 KB	Output is correct
7	Correct	93 ms	2760 KB	Output is correct
8	Correct	124 ms	3252 KB	Output is correct
9	Correct	211 ms	5464 KB	Output is correct
10	Correct	235 ms	5836 KB	Output is correct
11	Correct	119 ms	3216 KB	Output is correct
12	Correct	219 ms	5616 KB	Output is correct
13	Correct	136 ms	3424 KB	Output is correct
14	Correct	124 ms	3356 KB	Output is correct
15	Correct	223 ms	5676 KB	Output is correct
16	Correct	174 ms	4752 KB	Output is correct
17	Correct	247 ms	5828 KB	Output is correct
18	Correct	192 ms	5012 KB	Output is correct
19	Correct	223 ms	5480 KB	Output is correct
20	Correct	247 ms	5860 KB	Output is correct