The number of operations possible in 1 second.

Правка en2, от Number_72, 2023-05-01 13:57:36

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;
    unordered_map<int,int> cnt3 = cnt;
    int ans = 0;
    for (int i=1;i<=n;i++) {
        if (cnt[a[i]] && a[i] > 1) {
            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++) {
        if (a[i] > 1) {
            ans+=cnt3[1]*cnt3[a[i]]*cnt3[a[i]*a[i]];
            cnt3[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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Number_72 2023-05-01 13:58:11 208
en2 Английский Number_72 2023-05-01 13:57:36 0 Tiny change: ':\n\n~~~~~\n#include <' -> ':\n\n~~~~~#include <'
en1 Английский Number_72 2023-05-01 13:50:52 2261 Initial revision (published)