Submission #375716

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375716	2021-03-09T20:36:36 Z	YJU	PIN (CEOI10_pin)	C++14	80 / 100	1000 ms	12084 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);
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;
			}
		}
		REP(i,n){
			mm[id[i]].clear();
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Compilation message

pin.cpp:11:18: warning: overflow in conversion from 'long long int' to 'll' {aka 'int'} changes value from '1152921504606846976' to '0' [-Woverflow]
   11 | const ll INF=(1LL<<60);
      |              ~~~~^~~~~

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	6 ms	3436 KB	Output is correct
4	Correct	37 ms	4892 KB	Output is correct
5	Correct	47 ms	5276 KB	Output is correct
6	Correct	81 ms	5100 KB	Output is correct
7	Correct	64 ms	4844 KB	Output is correct
8	Correct	51 ms	5376 KB	Output is correct
9	Correct	85 ms	6716 KB	Output is correct
10	Correct	193 ms	7080 KB	Output is correct
11	Correct	87 ms	5484 KB	Output is correct
12	Correct	485 ms	7220 KB	Output is correct
13	Correct	207 ms	5628 KB	Output is correct
14	Correct	500 ms	5624 KB	Output is correct
15	Execution timed out	1094 ms	7672 KB	Time limit exceeded
16	Correct	80 ms	7116 KB	Output is correct
17	Correct	226 ms	9680 KB	Output is correct
18	Execution timed out	1084 ms	11024 KB	Time limit exceeded
19	Execution timed out	1097 ms	11444 KB	Time limit exceeded
20	Execution timed out	1095 ms	12084 KB	Time limit exceeded