[Gym] 102021F - Fighting Monsters

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 102021F - Fighting Monsters
Source            : Codeforces Gym
Category          : Finding Pattern
Algorithm         : Fibonacci Series
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll       long long int  
  
static const int maxn = 1e6 + 6;  
  
int fibo[maxn];  
int FIBO[maxn];  
int kototomo[maxn];  
int index[maxn];  
int arr[maxn];  
  
void calcFibo()  
{  
    int ptr = 0;  
    fibo[1] = 1;  
    kototomo[1] = ++ptr;  
    FIBO[ptr] = 1;  
    fibo[2] = 1;  
    for (int i = 3; ; i++)  
    {  
        ll fib = (ll)fibo[i-1] + (ll)fibo[i-2];  
        if (fib > 1000000) break;  
        fibo[i] = (int)fib;  
        kototomo[ fibo[i] ] = ++ptr;  
        FIBO[ptr] = fibo[i];   
    }  
}  
  
int main()  
{  
//    freopen("in.txt", "r", stdin);  
  
    calcFibo();  
  
    int n;  
    cin >> n;  
    for (int i = 1; i <= n; i++)  
    {  
        cin >> arr[i];  
        if (arr[i] == 1)  
        {  
            if (index[1] > 0)  
            {  
                cout << index[1] << " " << i << endl;  
                exit(0);  
            }  
        }  
        if (kototomo[ arr[i] ] > 0)  
        {  
            int l = FIBO[ kototomo[ arr[i] ] - 1 ];  
            int r = FIBO[ kototomo[ arr[i] ] ];  
            if (index[l] > 0)  
            {  
                cout << index[l] << " " << i << endl;  
                exit(0);  
            }  
        }  
        index[ arr[i] ] = i;  
    }  
    fill(begin(index), end(index), 0);  
    for (int i = n; i >= 1; i--)  
    {  
        if (arr[i] == 1)  
        {  
            if (index[1] > 0)  
            {  
                cout << index[1] << " " << i << endl;  
                exit(0);  
            }  
        }  
        if (kototomo[ arr[i] ] > 0)  
        {  
            int l = FIBO[ kototomo[ arr[i] ] - 1 ];  
            int r = FIBO[ kototomo[ arr[i] ] ];  
            if (index[l] > 0)  
            {  
                cout << index[l] << " " << i << endl;  
                exit(0);  
            }  
        }  
        index[ arr[i] ] = i;  
    }  
    cout << "impossible\n";  
}