Submission #375715

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375715	2021-03-09T20:35:46 Z	YJU	PIN (CEOI10_pin)	C++14	80 / 100	1000 ms	13480 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);
const ll INF=(1LL<<60);
#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];
unordered_map<ll,ll> mm[N];

ll num(char c){
	return ((c>='0'&&c<='9')?c-'0':10+c-'a');
}

ll vec(ll mask,ll id){
	ll tmp=0;
	REP(i,4)if((mask>>i)&1)tmp=tmp*37+v[id][i]+1;else tmp=tmp*37;
	return tmp;
}

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();
			for(ll bit=mask;;bit=(bit-1)&mask){
				ll val=vec(bit,i);
				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;
			}
		}
		memset(cnt,0,sizeof(cnt));
		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	3692 KB	Output is correct
2	Correct	8 ms	3820 KB	Output is correct
3	Correct	6 ms	3820 KB	Output is correct
4	Correct	39 ms	5784 KB	Output is correct
5	Correct	48 ms	6232 KB	Output is correct
6	Correct	80 ms	6188 KB	Output is correct
7	Correct	66 ms	5972 KB	Output is correct
8	Correct	53 ms	6444 KB	Output is correct
9	Correct	87 ms	8520 KB	Output is correct
10	Correct	189 ms	8700 KB	Output is correct
11	Correct	90 ms	6332 KB	Output is correct
12	Correct	483 ms	8828 KB	Output is correct
13	Correct	204 ms	6788 KB	Output is correct
14	Correct	485 ms	6652 KB	Output is correct
15	Execution timed out	1095 ms	8708 KB	Time limit exceeded
16	Correct	91 ms	8548 KB	Output is correct
17	Correct	231 ms	11492 KB	Output is correct
18	Execution timed out	1032 ms	12124 KB	Time limit exceeded
19	Execution timed out	1094 ms	12840 KB	Time limit exceeded
20	Execution timed out	1086 ms	13480 KB	Time limit exceeded