https://www.spoj.com/problems/ADAFIMBR/ can anyone please tell me what modification I can do in my code to accept this problem . It gives TLE to me right now .
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
#define ll int
#define intmax INT_MAX
#define pi 3.14159265358979323846
#define ff first
#define ss second
#define pb push_back
#define watch(x) cerr<<(#x)<<" "<<x<<"\n";
int mod=1e9+7;
const int MAXN = 1e5+2,MAXM=3e6+3;
int a[MAXN],k,ans[MAXM];
vector<int> fib(2),dp[MAXM];
inline int mex(int x){
unordered_map<int,int> m;
for(int i=0;i<(int)dp[x].size();i++) m[dp[x][i]]++;
int ap=0;
while(m[ap]) ap++;
return ap;
}
int main(){
int tt=1;
ios_base::sync_with_stdio(0);
cout.tie(0);
//~ cin>>tt;
while(tt--){
int n; cin>>n;
for(int i=0;i<n;i++) { cin>>a[i]; }
fib[0]=fib[1]=1;
for(int i=0;i<100;i++)if(fib[i]+fib[i+1]<=3e6)fib.pb(fib[i]+fib[i+1]); else break;
k=fib.size();
for(int i=0;i<=3e6;i++){
if(i>=1) {
ans[i]=mex(i);
}
for(int j=0;j<k;j++){
if(i+fib[j]>MAXM) continue;
else dp[i+fib[j]].pb(ans[i]);
}
}
int an=0;
for(int i=0;i<n;i++) an^=ans[a[i]];
if(an)cout<<"Ada\n";
else cout<<"Vinit\n";
}
return 0;
}
Full text and comments »