HELP WITH GRUNDY

Правка en1, от adyyy, 2020-07-14 11:05:34

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;
}

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский adyyy 2020-07-14 11:05:34 1715 Initial revision (published)