Submission #136844

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136844	2019-07-26T10:53:04 Z	choikiwon	PIN (CEOI10_pin)	C++17	100 / 100	438 ms	19512 KB

pin

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

const int maxn = 50010;

int N, D;
string pin[maxn];
int bcnt[16];
map<string, vector<string> > V[16];
map<string, int> cnt[16];

int main() {
    std::ios::sync_with_stdio(false);

    for(int i = 0; i < 16; i++) {
        for(int j = 0; j < 4; j++) if(i & (1 << j)) bcnt[i]++;
    }

    cin >> N >> D;
    D = 4 - D;

    for(int i = 0; i < N; i++) {
        cin >> pin[i];
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < 16; j++) {
            if(bcnt[j] != D) continue;

            string x, y;
            for(int k = 0; k < 4; k++) {
                if(j & (1 << k)) x.push_back(pin[i][k]);
                else y.push_back(pin[i][k]);
            }
            V[j][x].push_back(y);
        }
    }

    int ans = 0;
    for(int mask = 0; mask < 16; mask++) {
        if(bcnt[mask] != D) continue;

        for(auto it = V[mask].begin(); it != V[mask].end(); it++) {
            for(int i = 0; i < (1 << (4 - D)); i++) cnt[i].clear();

            vector<string> X = it->second;
            for(int i = 0; i < X.size(); i++) {
                for(int j = 0; j < (1 << (4 - D)); j++) {
                    string x;
                    for(int k = 0; k < 4; k++) if(j & (1 << k)) x.push_back(X[i][k]);
                    cnt[j][x]++;
                }
            }
            for(int m = 0; m < 16; m++) {
                for(auto it = cnt[m].begin(); it != cnt[m].end(); it++) {
                    if(bcnt[m] % 2) ans -= 1LL * it->second * (it->second - 1) / 2;
                    else ans += 1LL * it->second * (it->second - 1) / 2;
                }
            }
        }
    }
    cout << ans;
}

Compilation message

pin.cpp: In function 'int main()':
pin.cpp:47:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < X.size(); i++) {
                            ~~^~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	2680 KB	Output is correct
2	Correct	13 ms	2596 KB	Output is correct
3	Correct	10 ms	2552 KB	Output is correct
4	Correct	82 ms	7544 KB	Output is correct
5	Correct	85 ms	8568 KB	Output is correct
6	Correct	119 ms	8952 KB	Output is correct
7	Correct	96 ms	8824 KB	Output is correct
8	Correct	94 ms	9208 KB	Output is correct
9	Correct	150 ms	13356 KB	Output is correct
10	Correct	235 ms	15608 KB	Output is correct
11	Correct	127 ms	9004 KB	Output is correct
12	Correct	240 ms	9848 KB	Output is correct
13	Correct	154 ms	6264 KB	Output is correct
14	Correct	113 ms	7080 KB	Output is correct
15	Correct	194 ms	9988 KB	Output is correct
16	Correct	195 ms	16760 KB	Output is correct
17	Correct	340 ms	19512 KB	Output is correct
18	Correct	365 ms	16080 KB	Output is correct
19	Correct	433 ms	17852 KB	Output is correct
20	Correct	438 ms	19360 KB	Output is correct