Submission #375712

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375712	2021-03-09T19:57:37 Z	YJU	PIN (CEOI10_pin)	C++14	30 / 100	161 ms	11792 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 num(char c){
	return ((c>='0'&&c<='9')?c-'0':10+c-'a');
}

ll n,d,ans=0;
vector<ll> v[N];
string s;

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

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>d;
	REP(i,n){
		cin>>s;
		REP(j,4)v[i].pb(num(s[j]));
	}
	for(ll bit=0;bit<(1<<4);++bit){
		if(count(bit)!=4-d)continue;
		vector<ll> vid,vin;
		REP(i,n){
			id[i]=in[i]=0;
			REP(j,4)if((bit>>j)&1){
				id[i]=id[i]*36+v[i][j];
			}else in[i]=in[i]*36+v[i][j];
			vid.pb(id[i]);
			vin.pb(in[i]);
		}
		sort(vid.begin(),vid.end());
		vid.erase(unique(vid.begin(),vid.end()),vid.end());
		sort(vin.begin(),vin.end());
		vin.erase(unique(vin.begin(),vin.end()),vin.end());
		REP(i,n){
			id[i]=lwb(vid.begin(),vid.end(),id[i])-vid.begin();
			in[i]=lwb(vin.begin(),vin.end(),in[i])-vin.begin();
			ans+=cnt[id[i]]-mm[id[i]][in[i]];
			++mm[id[i]][in[i]];++cnt[id[i]];
		}
		memset(cnt,0,sizeof(cnt));
		REP(i,n)mm[i].clear();
	}
	cout<<ans<<"\n";
	return 0;
}

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4972 KB	Output is correct
2	Incorrect	7 ms	4844 KB	Output isn't correct
3	Incorrect	4 ms	4844 KB	Output isn't correct
4	Correct	43 ms	7664 KB	Output is correct
5	Correct	52 ms	8288 KB	Output is correct
6	Incorrect	66 ms	8276 KB	Output isn't correct
7	Incorrect	53 ms	7408 KB	Output isn't correct
8	Correct	58 ms	8576 KB	Output is correct
9	Correct	94 ms	11336 KB	Output is correct
10	Incorrect	131 ms	11668 KB	Output isn't correct
11	Incorrect	71 ms	8452 KB	Output isn't correct
12	Incorrect	90 ms	10876 KB	Output isn't correct
13	Incorrect	57 ms	8640 KB	Output isn't correct
14	Incorrect	20 ms	7960 KB	Output isn't correct
15	Incorrect	33 ms	10592 KB	Output isn't correct
16	Correct	81 ms	10164 KB	Output is correct
17	Incorrect	161 ms	11792 KB	Output isn't correct
18	Incorrect	27 ms	9488 KB	Output isn't correct
19	Incorrect	31 ms	10208 KB	Output isn't correct
20	Incorrect	35 ms	10848 KB	Output isn't correct