Submission #480234

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
480234	2021-10-15T10:30:23 Z	mohamedsobhi777	PIN (CEOI10_pin)	C++14	100 / 100	218 ms	17932 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 - 1) & u){
                            if(u != sub)
                                   dp[sub] -= dp[u] ; 
                            if(sub == 0)break; 
                     }
              }
              for(auto u : masks){
                     if(__builtin_popcount(u) == d){
                            ret += dp[u] ; 
                     }
              }

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	7012 KB	Output is correct
2	Correct	8 ms	6988 KB	Output is correct
3	Correct	7 ms	6988 KB	Output is correct
4	Correct	48 ms	8844 KB	Output is correct
5	Correct	63 ms	9244 KB	Output is correct
6	Correct	60 ms	9164 KB	Output is correct
7	Correct	47 ms	8904 KB	Output is correct
8	Correct	71 ms	9396 KB	Output is correct
9	Correct	112 ms	10416 KB	Output is correct
10	Correct	117 ms	10740 KB	Output is correct
11	Correct	61 ms	9284 KB	Output is correct
12	Correct	119 ms	10672 KB	Output is correct
13	Correct	67 ms	9436 KB	Output is correct
14	Correct	67 ms	9284 KB	Output is correct
15	Correct	114 ms	10692 KB	Output is correct
16	Correct	131 ms	15044 KB	Output is correct
17	Correct	218 ms	17932 KB	Output is correct
18	Correct	150 ms	15876 KB	Output is correct
19	Correct	180 ms	17080 KB	Output is correct
20	Correct	217 ms	17864 KB	Output is correct