Submission #375728

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375728	2021-03-09T21:28:11 Z	YJU	PIN (CEOI10_pin)	C++14	100 / 100	513 ms	24692 KB

pin

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+9;
const ll MOD2=998244353;
const ll N=5e4+5;
const ld pi=acos(-1);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
#define count(_a) (ll)__builtin_popcount(_a)
 
ll n,d,v[N][4],u[16];
string s;
map<vector<ll>,ll> mm;
ll ans[5];
 
ll num(char c){
	return ((c>='0'&&c<='9')?c-'0':10+c-'a');
}
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>d;
	REP(i,n){
		cin>>s;
		REP(j,4)v[i][j]=num(s[j]);
		for(ll mask=0;mask<(1<<4);++mask){
			vector<ll> vec;
			REP(j,4){
				if((mask>>j)&1)vec.pb(v[i][j]+1);
				else vec.pb(0);
			}
			++mm[vec];
		}
	}
	for(auto i:mm){
		ll bit=(1<<4)-1;
		REP(j,4){
			if(i.X[j]==0)bit^=(1<<j);
		}
		u[bit]+=((i.Y)*(i.Y-1)/2);
	}
	for(int i=(1<<4)-1;i>=0;i--){
		for(int j=0;j<(1<<4);j++){
			if(j!=i&&(j&i)==i){
				u[i]-=u[j];
			}
		}
		ans[count(i)]+=u[i];
	}
	cout<<ans[4-d]<<"\n";
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	1516 KB	Output is correct
2	Correct	10 ms	1388 KB	Output is correct
3	Correct	8 ms	1260 KB	Output is correct
4	Correct	122 ms	5788 KB	Output is correct
5	Correct	152 ms	6508 KB	Output is correct
6	Correct	146 ms	6528 KB	Output is correct
7	Correct	126 ms	5740 KB	Output is correct
8	Correct	167 ms	6892 KB	Output is correct
9	Correct	277 ms	9580 KB	Output is correct
10	Correct	322 ms	10348 KB	Output is correct
11	Correct	164 ms	6764 KB	Output is correct
12	Correct	293 ms	9964 KB	Output is correct
13	Correct	185 ms	7404 KB	Output is correct
14	Correct	175 ms	6892 KB	Output is correct
15	Correct	293 ms	9964 KB	Output is correct
16	Correct	324 ms	18612 KB	Output is correct
17	Correct	502 ms	24684 KB	Output is correct
18	Correct	367 ms	20332 KB	Output is correct
19	Correct	470 ms	22880 KB	Output is correct
20	Correct	513 ms	24692 KB	Output is correct