Submission #375719

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375719	2021-03-09T20:51:49 Z	YJU	PIN (CEOI10_pin)	C++14	80 / 100	1000 ms	11960 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],dp[16],pre[16];
unordered_map<ll,ll> mm[N];
vector<ll> vid;

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;
		vid.clear();
		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)pre[(1<<j)]=P*((mask>>j)&1?v[i][j]+1:0);
			for(ll bit=0;bit<(1<<4);++bit){
				dp[bit]=dp[bit-(bit&-bit)]+pre[(bit&-bit)];
				if((bit|mask)>mask)continue;
				ll val=dp[bit];
				ans+=(count(bit)&1?-1:1)*mm[id[i]][val];
				++mm[id[i]][val];
			}
		}
		REP(i,n){
			mm[id[i]].clear();
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Subtask #1

80.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3308 KB	Output is correct
2	Correct	7 ms	3308 KB	Output is correct
3	Correct	7 ms	3436 KB	Output is correct
4	Correct	39 ms	4844 KB	Output is correct
5	Correct	47 ms	5100 KB	Output is correct
6	Correct	81 ms	5100 KB	Output is correct
7	Correct	71 ms	4844 KB	Output is correct
8	Correct	54 ms	5356 KB	Output is correct
9	Correct	88 ms	6512 KB	Output is correct
10	Correct	198 ms	6896 KB	Output is correct
11	Correct	86 ms	5228 KB	Output is correct
12	Correct	496 ms	7260 KB	Output is correct
13	Correct	213 ms	5612 KB	Output is correct
14	Correct	493 ms	5624 KB	Output is correct
15	Execution timed out	1085 ms	7676 KB	Time limit exceeded
16	Correct	87 ms	6768 KB	Output is correct
17	Correct	294 ms	9840 KB	Output is correct
18	Execution timed out	1083 ms	11028 KB	Time limit exceeded
19	Execution timed out	1090 ms	11448 KB	Time limit exceeded
20	Execution timed out	1059 ms	11960 KB	Time limit exceeded