Submission #375717

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375717	2021-03-09T20:42:44 Z	YJU	PIN (CEOI10_pin)	C++14	30 / 100	60 ms	5612 KB

pin

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int 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,ans=0,v[N][4];
string s;

ll id[N],cnt[N],dp[16];
unordered_map<ll,ll> mm[N];

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){
		if(count(mask)!=d)continue;
		vector<ll> vid;
		REP(i,n){
			id[i]=0;
			REP(j,4)if(!((mask>>j)&1)){
				id[i]=id[i]*36+v[i][j];
			}
			vid.pb(id[i]);
		}
		sort(vid.begin(),vid.end());
		vid.erase(unique(vid.begin(),vid.end()),vid.end());
		REP(i,n){
			id[i]=lwb(vid.begin(),vid.end(),id[i])-vid.begin();
			memset(dp,0,sizeof(dp));
			for(int j=0,P=1;j<4;j++,P*=37)dp[(1<<j)]=P*v[i][j];
			for(ll bit=0;bit<(1<<4);++bit){
				dp[bit]=dp[bit-(bit&-bit)]+dp[(bit&-bit)];
				if((bit|mask)>mask)continue;
				ll val=dp[bit];
				if(count(bit)&1){
					ans-=mm[id[i]][val];
					++mm[id[i]][val];
				}else{
					ans+=mm[id[i]][val];
					++mm[id[i]][val];
				}
				if(bit==0)break;
			}
		}
		REP(i,n){
			mm[id[i]].clear();
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3180 KB	Output is correct
2	Incorrect	4 ms	3180 KB	Output isn't correct
3	Incorrect	2 ms	3180 KB	Output isn't correct
4	Correct	24 ms	4124 KB	Output is correct
5	Correct	27 ms	4104 KB	Output is correct
6	Incorrect	26 ms	3868 KB	Output isn't correct
7	Incorrect	21 ms	3752 KB	Output isn't correct
8	Correct	29 ms	4096 KB	Output is correct
9	Correct	45 ms	4708 KB	Output is correct
10	Incorrect	51 ms	4608 KB	Output isn't correct
11	Incorrect	27 ms	3932 KB	Output isn't correct
12	Incorrect	24 ms	4480 KB	Output isn't correct
13	Incorrect	16 ms	3980 KB	Output isn't correct
14	Incorrect	6 ms	3820 KB	Output isn't correct
15	Incorrect	9 ms	4356 KB	Output isn't correct
16	Correct	52 ms	5612 KB	Output is correct
17	Incorrect	60 ms	4652 KB	Output isn't correct
18	Incorrect	8 ms	4204 KB	Output isn't correct
19	Incorrect	8 ms	4332 KB	Output isn't correct
20	Incorrect	9 ms	4336 KB	Output isn't correct