Submission #496425

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
496425	2021-12-21T07:47:28 Z	XBoRickie	PIN (CEOI10_pin)	C++14	90 / 100	199 ms	11668 KB

pin

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;

#define fastIO ios::sync_with_stdio(false), cin.tie(NULL)
#define forw(i, l, r) for( int i = (l) ; i < (r) ; i++ )
#define forb(i, r, l) for( int i = (r) ; i >= (l) ; i-- )
#define log2i(x) (64 - __builtin_clzll(1ll * (x)) - 1)
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define Pi acos(-1.0l)
#define sz(x) int(x.size())
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define debug(x) cerr << #x << " = " << x << '\n';

const int N = 50007;
const int base = 311;
int n, d;
int comb[5][5];
map<ll, int> cnt[16];

int main() {
    fastIO;

    comb[0][0] = 1;
    forw(i, 1, 5) forw(j, 0, i + 1) {
        comb[i][j] = comb[i - 1][j];
        if(j) comb[i][j] += comb[i - 1][j - 1];
    }
    cin >> n >> d; d = 4 - d;
    forw(i, 0, n) {
        string st; cin >> st;
        forw(j, 0, 16) {
            ll sum = 0;
            forw(k, 0, 4) if(getBit(j, k)) sum = sum * base + st[k];
            cnt[j][sum]++;
        }
    }

    ll ans = 0;
    forw(i, 0, 16) {
        if(numBit(i) < d) continue;
        ll val = 0;
        for(auto x:cnt[i]) val += x.se * (x.se - 1) / 2;
        val *= comb[numBit(i)][numBit(i) - d];

        if((numBit(i) - d) & 1) ans -= val;
        else ans += val;
    }
    cout << ans;
    return 0;
}

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	844 KB	Output is correct
2	Correct	3 ms	716 KB	Output is correct
3	Correct	3 ms	716 KB	Output is correct
4	Correct	36 ms	2544 KB	Output is correct
5	Correct	44 ms	2852 KB	Output is correct
6	Correct	45 ms	2972 KB	Output is correct
7	Correct	35 ms	2584 KB	Output is correct
8	Correct	52 ms	3084 KB	Output is correct
9	Correct	90 ms	4172 KB	Output is correct
10	Correct	91 ms	4516 KB	Output is correct
11	Correct	48 ms	2988 KB	Output is correct
12	Correct	85 ms	4264 KB	Output is correct
13	Correct	57 ms	3244 KB	Output is correct
14	Correct	49 ms	3068 KB	Output is correct
15	Incorrect	89 ms	4336 KB	Output isn't correct
16	Correct	111 ms	8900 KB	Output is correct
17	Correct	199 ms	11668 KB	Output is correct
18	Correct	144 ms	9608 KB	Output is correct
19	Correct	176 ms	10692 KB	Output is correct
20	Incorrect	178 ms	11564 KB	Output isn't correct