Submission #142826

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
142826	2019-08-11T11:19:10 Z	popovicirobert	PIN (CEOI10_pin)	C++14	0 / 100	247 ms	5888 KB

pin

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


/*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 < 10; 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	7 ms	504 KB	Output isn't correct
4	Incorrect	90 ms	2764 KB	Output isn't correct
5	Incorrect	111 ms	3484 KB	Output isn't correct
6	Incorrect	110 ms	3124 KB	Output isn't correct
7	Incorrect	91 ms	2756 KB	Output isn't correct
8	Incorrect	124 ms	3368 KB	Output isn't correct
9	Incorrect	207 ms	5476 KB	Output isn't correct
10	Incorrect	230 ms	5860 KB	Output isn't correct
11	Incorrect	118 ms	3232 KB	Output isn't correct
12	Incorrect	215 ms	5784 KB	Output isn't correct
13	Incorrect	130 ms	3568 KB	Output isn't correct
14	Incorrect	119 ms	3276 KB	Output isn't correct
15	Incorrect	220 ms	5632 KB	Output isn't correct
16	Incorrect	169 ms	4720 KB	Output isn't correct
17	Incorrect	244 ms	5888 KB	Output isn't correct
18	Incorrect	190 ms	5016 KB	Output isn't correct
19	Incorrect	220 ms	5460 KB	Output isn't correct
20	Incorrect	247 ms	5864 KB	Output isn't correct