Submission #142828

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
142828	2019-08-11T11:21:37 Z	popovicirobert	PIN (CEOI10_pin)	C++14	0 / 100	248 ms	5964 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 - 1);
            i = j;
        }
        return ans;
    }
    else {
        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][i - j];
        }
    }
    cout << ways[d];

    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	8 ms	504 KB	Output isn't correct
2	Incorrect	8 ms	504 KB	Output isn't correct
3	Incorrect	6 ms	504 KB	Output isn't correct
4	Incorrect	93 ms	2856 KB	Output isn't correct
5	Incorrect	112 ms	3124 KB	Output isn't correct
6	Incorrect	113 ms	3208 KB	Output isn't correct
7	Incorrect	92 ms	2756 KB	Output isn't correct
8	Incorrect	124 ms	3456 KB	Output isn't correct
9	Incorrect	208 ms	5448 KB	Output isn't correct
10	Incorrect	231 ms	5792 KB	Output isn't correct
11	Incorrect	120 ms	3208 KB	Output isn't correct
12	Incorrect	218 ms	5716 KB	Output isn't correct
13	Incorrect	133 ms	3460 KB	Output isn't correct
14	Incorrect	122 ms	3276 KB	Output isn't correct
15	Incorrect	222 ms	5668 KB	Output isn't correct
16	Incorrect	172 ms	4720 KB	Output isn't correct
17	Incorrect	247 ms	5964 KB	Output isn't correct
18	Incorrect	193 ms	5088 KB	Output isn't correct
19	Incorrect	223 ms	5444 KB	Output isn't correct
20	Incorrect	248 ms	5904 KB	Output isn't correct