1109 - False Ordering

Problem Link

প্রথমত যে সংখ্যাটি দেওয়া হবে তার ডিভিজর এর সংখ্যা বের করতে হবে। এখন প্রতিটির জন্য এইভাবে বের করে হিসাব করতে অনেক সময় লাগবে ,যার জন্য TLE খেতে হবে। এইজন্য pre-calculation করে নিব। ১ থেকে ১০০০ পর্যন্ত সব কয়টি সংখ্যার জন্য ডিভিজর এর সংখ্যা বের করে একটা array তে রাখব, তারপর ওই সংখ্যাগুলো প্রব্লেমে দেওয়া শর্ত অনুযায়ী আরেটা array তে সাজিয়ে রাখব।

My Solution in C++:

#include<bits/stdc++.h>
using namespace std;
vector<int>v[1001];
vector<int>m[33];
vector<int>ans;

void cal()
{
    for(int n = 1; n <= 1000; n++)
    {
        int k = n;
        for (int i=1; i<=sqrt(n); i++)
        {
            if (n%i==0)
            {
                if (n/i == i)
                    v[k].push_back(i);
                else
                {
                    v[k].push_back(i);
                    v[k].push_back(n/i);
                }
            }
        }
    }
    for(int i = 1; i <= 32; i++)
    {
        for(int j = 1; j <= 1000; j++)
        {
            int q = v[j].size();
            if(i==q)
            {
                m[i].push_back(j);
            }
        }
    }
    for(int i = 1; i <= 32; i++)
    {
        for(int s = m[i].size()-1; s >=0; s--)
        {
            ans.push_back(m[i][s]);
        }
    }
}

int main()
{
    cal();
    int T, n;
    cin>>T;
    for(int t = 1; t <= T; t++)
    {
        cin>>n;
        cout<<"Case "<<t<<": "<<ans[n-1]<<endl;
    }

    return 0;
}