Submission #136844

#	Time	Username	Problem	Language	Result	Execution time	Memory
136844		choikiwon	PIN (CEOI10_pin)	C++17	100 / 100	438 ms	19512 KiB

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 (stderr)

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 / 100