Submission #1119125

#TimeUsernameProblemLanguageResultExecution timeMemory
1119125MinbaevPIN (CEOI10_pin)C++17
40 / 100
65 ms10244 KiB
#include <bits/stdc++.h> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; int n,m,k,q; vector<int>vis(2e6); void solve(){ cin >> n >> k; vector<string>v(n); for(auto &to:v)cin >> to; int res = 0; if(n <= 2000){ for(int i = 0;i<n;i++){ for(int j = i+1;j<n;j++){ int cnt = 0; for(int l = 0;l<4;l++){ if(v[i][l] != v[j][l])cnt += 1; } if(cnt == k)res += 1; } } } else{ int cnt = 1; map<char,int>mp; vector<int>pw(4), vs(n); pw[0] = 1; pw[1] = 37; pw[2] = 37*37; pw[3] = 37*37*37; for(int l = 0;l<=9;l++)mp['0'+l] = cnt++; for(int l = 0;l<26;l++)mp['a'+l] = cnt++; if(k == 1){ for(int j = 0;j<n;j++){ string to = v[j]; int cont = 0; for(int i = 0;i<4;i++){ cont += (pw[i]*mp[to[i]]); } vis[cont] += 1; vs[j] = cont; } for(int l = 0;l<n;l++){ string to = v[l]; for(int i = 0;i<4;i++){ int u = mp[v[l][i]]; for(int j = 1;j<=36;j++){ int cont = vs[l]; cont -= pw[i]*u; cont += pw[i]*j; res += vis[cont]; } } res -= vis[vs[l]]*4; vis[vs[l]] -= 1; } } if(k == 2){ for(int j = 0;j<n;j++){ string to = v[j]; int cont = 0; for(int i = 0;i<4;i++){ cont += (pw[i]*mp[to[i]]); } vis[cont] += 1; vs[j] = cont; } for(int j = 0;j<n;j++){ for(int l = 0;l<4;l++){ for(int r = l + 1;r<4;r++){ int cont = vs[j]; cont -= pw[l]*mp[v[j][l]]; cont -= pw[r]*mp[v[j][r]]; vis[cont] += 1; } } } for(int j = 0;j<n;j++){ for(int l = 0;l<4;l++){ for(int r = l + 1;r<4;r++){ int cont = vs[j]; cont -= pw[l]*mp[v[j][l]]; cont -= pw[r]*mp[v[j][r]]; res += vis[cont]; } } } } } cout << res << "\n"; } /* */ signed main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); int tt=1;//cin>>tt; while(tt--)solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...