Submission #142831

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
142831	2019-08-11T11:33:55 Z	popovicirobert	PIN (CEOI10_pin)	C++14	0 / 100	249 ms	5664 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 {
        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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	8 ms	508 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	92 ms	2668 KB	Output isn't correct
5	Incorrect	110 ms	3008 KB	Output isn't correct
6	Incorrect	111 ms	3012 KB	Output isn't correct
7	Incorrect	91 ms	2700 KB	Output isn't correct
8	Incorrect	121 ms	3152 KB	Output isn't correct
9	Incorrect	206 ms	5268 KB	Output isn't correct
10	Incorrect	226 ms	5576 KB	Output isn't correct
11	Incorrect	119 ms	3188 KB	Output isn't correct
12	Incorrect	219 ms	5504 KB	Output isn't correct
13	Incorrect	139 ms	3280 KB	Output isn't correct
14	Incorrect	126 ms	3132 KB	Output isn't correct
15	Incorrect	218 ms	5392 KB	Output isn't correct
16	Incorrect	171 ms	4528 KB	Output isn't correct
17	Incorrect	244 ms	5580 KB	Output isn't correct
18	Incorrect	192 ms	4808 KB	Output isn't correct
19	Incorrect	220 ms	5224 KB	Output isn't correct
20	Incorrect	249 ms	5664 KB	Output isn't correct