用unordered_map导致复杂度爆了的问题
查看原帖
用unordered_map导致复杂度爆了的问题
738749
Sasya楼主2023/3/11 16:07

大佬们,不知道为什么用unordered_map就过不了,但是用数组就可以过。unordered_map遍历的复杂度难道比数组高很多吗....

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
using ll= long long int;
const ll rr=1e9+7;

int main(){
	vector<ll> mp(5005,0);
	int n;cin>>n;
	rep(i,1,n){
		int p;cin>>p;
		mp[p]++;
	}
	
	ll sum=0;
	for(int i=1;i<=2499;i++){
		if(mp[i]==0)continue;
		for(int j=i+1;i+j<=5000;j++){
			if(mp[j]==0)continue;
			if(mp[i+j]>=2){
				sum+=mp[i]*mp[j]*mp[i+j]*(mp[i+j]-1)/2;
				if(sum>=rr)sum%=rr;
			}
		}
	}
	for(int i=1;i<=2500;i++){
		if(mp[i]<2)continue;
		if(mp[i*2]>=2){
			sum+=mp[i]*(mp[i]-1)/2*mp[i*2]*(mp[i*2]-1)/2;
			if(sum>=rr)sum%=rr;
		}
	}
	cout<<sum%rr;
}
2023/3/11 16:07
加载中...