Hello Codeforces, today I was solving this problem:1822G1 - Magic Triples (Easy Version). I wrote a very simple brute force solution. here is my code:
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define inf 2e18
#define endl '\n'
#define int long long
#define F(xxx,yyy,zzz) for (int xxx=yyy;xxx<zzz;xxx++)
int MOD = 1000000007;
int mul(int x, int y){
return ((x % MOD) * (y % MOD)) % MOD;
}
int add(int x, int y){
return ((x%MOD)+(y%MOD))%MOD;
}
int exp(int x, int y){
int ans = 1;
while (y){
if (y % 2) ans = mul(ans, x);
x = mul(x, x);
y /= 2;
}
return ans;
}
int divide(int x, int y){
return mul(x, exp(y, MOD - 2));
}
using namespace std;
void solve(){
int n;
cin >> n;
int a[n+1];
for (int i=1;i<=n;i++) cin >> a[i];
sort(a+1,a+n+1);
unordered_map<int,int> cnt;
for (int i=1;i<=n;i++) cnt[a[i]]++;
unordered_map<int,int> cnt2 = cnt;
int ans = 0;
for (int i=1;i<=n;i++) {
if (cnt[a[i]]) {
for (int b=2;a[i]*b*b<=a[n];b++) {
ans+= cnt[a[i]]*cnt[a[i]*b]*cnt[a[i]*b*b];
}
cnt[a[i]] = 0;
}
}
for (int i=1;i<=n;i++) {
ans+= max(0ll,(cnt2[a[i]])*(cnt2[a[i]]-1)*(cnt2[a[i]]-2));
cnt2[a[i]] = 0;
}
cout << ans << endl;
}
signed main()
{
#ifdef Local
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int tc = 1;
cin >> tc;
while (tc--)solve();
}
I estimated that this algorithm would make at most 2e8 operations in total but it gets TLE on TC 14. N goes upto 2e5 and the elements of A go upto 1e6 so b would iterate upto at most 1e3. So I am a bit confused. I reckon it has something to do with the unordered map but I am not sure. I would be happy if someone pointed out the mistake.