Sukarna_Paul's blog

By Sukarna_Paul, history, 8 months ago, , I was solving the problem from SPOJ Link . But my solution is getting TLE. Please help me out!

Here is my solution :

#pragma warning(disable:4786)
#pragma warning(disable:4996)
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define pli pair<long long , int>
#define pil pair<int ,long long>
#define pi acos(-1)
#define pb push_back
#define mkp make_pair
#define all(a) a.begin(), a.end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define MAX 300005
#define INF 0x3f3f3f3f
template <class T> inline T bigmod(T p,T e,T M){ll ret = 1LL;for(; e > 0LL; e >>= 1LL){if(e & 1LL) ret = (ret * p) % M;p = (p * p) % M;}return (T)ret;}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}   // M is prime}
using namespace std;

vector <ll> prime;
bitset <100000010> bs;

void sieve ()
{
bs.set ();
prime.pb(2LL);
for (ll i = 3; i < 100000000; i+=2)
{
if (bs[i])
{
prime.pb(i);
for (ll j = i * i; j < 10000000; j += i+i)
{
bs[j] = 0;
}
}
}
}

int main(){
IOS
//freopen("output.txt","w",stdout);
sieve();
int i=0;
unordered_map<int,int>r,c;

for(auto it=prime.begin();it!=prime.end();){
i++;
for(int j=1;j<=i;j++){
r[(*it)]=i;
c[(*it)]=j;
it++;
}
}
int t;
cin>>t;
for(int i=0;i<t;i++){
int a;
cin>>a;
if(r[a]==0){
cout<<"-1"<<endl;
continue;
}
cout<<r[a]<<" "<<c[a]<<endl;

}
} Comments (5)
 » Maybe this can help. https://codeforces.com/blog/entry/54090
•  » » 8 months ago, # ^ | ← Rev. 2 →   Ok thanks , let me see
 » Reading the comments in SPOJ, it seems the time limit is a bit strict (classic SPOJ). So, regardless of the sieve implementation, something that may help in this case is changing to "\n".I understand that flushes the buffer every time.If you want to test correctness there seems to be a tutorial version after the examples.Happy Coding!
•  » » Sorry , but it didn't work . Still TLE :(
 » You may try to use Segmented Sieve which is claimed to have less cache memory misses when n is large.