Submission #142829

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
142829	2019-08-11T11:27:33 Z	popovicirobert	PIN (CEOI10_pin)	C++14	0 / 100	256 ms	5896 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][4 - i];
        }
    }
    cout << ways[d];

    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	9 ms	504 KB	Output isn't correct
2	Incorrect	8 ms	508 KB	Output isn't correct
3	Incorrect	7 ms	504 KB	Output isn't correct
4	Incorrect	93 ms	2764 KB	Output isn't correct
5	Incorrect	113 ms	3136 KB	Output isn't correct
6	Incorrect	113 ms	3276 KB	Output isn't correct
7	Incorrect	94 ms	2796 KB	Output isn't correct
8	Incorrect	126 ms	3348 KB	Output isn't correct
9	Incorrect	210 ms	5520 KB	Output isn't correct
10	Incorrect	230 ms	5820 KB	Output isn't correct
11	Incorrect	120 ms	3236 KB	Output isn't correct
12	Incorrect	222 ms	5644 KB	Output isn't correct
13	Incorrect	133 ms	3436 KB	Output isn't correct
14	Incorrect	123 ms	3244 KB	Output isn't correct
15	Incorrect	222 ms	5768 KB	Output isn't correct
16	Incorrect	181 ms	4832 KB	Output isn't correct
17	Incorrect	249 ms	5896 KB	Output isn't correct
18	Incorrect	195 ms	5132 KB	Output isn't correct
19	Incorrect	235 ms	5616 KB	Output isn't correct
20	Incorrect	256 ms	5840 KB	Output isn't correct