Submission #480232

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
480232	2021-10-15T10:27:02 Z	mohamedsobhi777	PIN (CEOI10_pin)	C++14	70 / 100	216 ms	18084 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 = 1;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	7 ms	7096 KB	Output is correct
2	Correct	7 ms	6988 KB	Output is correct
3	Incorrect	6 ms	6988 KB	Output isn't correct
4	Correct	48 ms	8856 KB	Output is correct
5	Correct	57 ms	9160 KB	Output is correct
6	Correct	64 ms	9184 KB	Output is correct
7	Correct	46 ms	8872 KB	Output is correct
8	Correct	62 ms	9328 KB	Output is correct
9	Correct	104 ms	10356 KB	Output is correct
10	Correct	107 ms	10668 KB	Output is correct
11	Correct	58 ms	9232 KB	Output is correct
12	Correct	104 ms	10660 KB	Output is correct
13	Correct	71 ms	9540 KB	Output is correct
14	Incorrect	62 ms	9272 KB	Output isn't correct
15	Incorrect	108 ms	10640 KB	Output isn't correct
16	Correct	126 ms	15152 KB	Output is correct
17	Correct	216 ms	18084 KB	Output is correct
18	Incorrect	151 ms	16068 KB	Output isn't correct
19	Incorrect	187 ms	17000 KB	Output isn't correct
20	Incorrect	210 ms	17980 KB	Output isn't correct