Submission #480233

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
480233	2021-10-15T10:28:46 Z	mohamedsobhi777	PIN (CEOI10_pin)	C++14	70 / 100	219 ms	17928 KB

pin

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 7;
int n, d; 
long long ans ; 
string st[N] ; 
map<long long,long long> atm[17] ; 

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       cin >> n >> d ; 
       d = 4 - d; 
       for(int i = 0 ;i < n; ++ i){
              cin >> st[i] ; 
       }
       vector<int> masks ; 
       for(int i = 0;i < 16 ;++ i){
              masks.push_back(i) ; 
       }
       sort(masks.begin(), masks.end(), [&](int x, int y){
              return __builtin_popcount(x) > __builtin_popcount(y) ; 
       }) ; 
       for(int i = 0 ;i < n; ++ i ){
              long long ret = 0 ; 
              vector<long long> dp(18, 0) ; 
              for(auto u : masks){
                     int hsh = 0 ; 
                     for(int k = 0 ; k < 4 ; ++ k){
                            if(u&(1<<k)){
                                   hsh = hsh * 150 + st[i][k] ; 
                            }
                     }
                     dp[u] += atm[u][hsh]++ ; 
                     for(int sub = u ; sub ; sub = (sub - 1) & u){
                            if(u != sub)
                                   dp[sub] -= dp[u] ; 
                     }
              }
              for(auto u : masks){
                     if(__builtin_popcount(u) == d){
                            ret += dp[u] ; 
                     }
              }

              ans += ret ; 
       }
       cout << ans ; 
       return 0;
}

Subtask #1

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	7116 KB	Output is correct
2	Correct	7 ms	6988 KB	Output is correct
3	Incorrect	9 ms	6992 KB	Output isn't correct
4	Correct	64 ms	8952 KB	Output is correct
5	Correct	57 ms	9232 KB	Output is correct
6	Correct	63 ms	9180 KB	Output is correct
7	Correct	51 ms	8900 KB	Output is correct
8	Correct	64 ms	9396 KB	Output is correct
9	Correct	98 ms	10448 KB	Output is correct
10	Correct	143 ms	10688 KB	Output is correct
11	Correct	60 ms	9328 KB	Output is correct
12	Correct	113 ms	10584 KB	Output is correct
13	Correct	68 ms	9540 KB	Output is correct
14	Incorrect	65 ms	9352 KB	Output isn't correct
15	Incorrect	107 ms	10556 KB	Output isn't correct
16	Correct	129 ms	15108 KB	Output is correct
17	Correct	209 ms	17860 KB	Output is correct
18	Incorrect	153 ms	16020 KB	Output isn't correct
19	Incorrect	187 ms	16976 KB	Output isn't correct
20	Incorrect	219 ms	17928 KB	Output isn't correct