fork download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<cstring>
  5. #include<map>
  6. using namespace std;
  7. typedef long long ll;
  8.  
  9. map< ll , bool > memo;
  10.  
  11. ll pow2[50];
  12.  
  13. #define maxn 150000000
  14.  
  15. bool memo2[maxn];
  16. bool done[maxn];
  17.  
  18. bool solve( ll curr )
  19. {
  20.     if( curr < maxn )
  21. 	{
  22. 		if( done[curr] )
  23. 			return memo2[curr];
  24. 	}
  25. 	else if( memo.count(curr) )
  26. 		return memo[curr];
  27.  
  28.    bool ans=false;
  29.  
  30.    for(int k=32;k>=0;k--)
  31.    {  
  32. 	   if( pow2[k] >= curr )
  33. 		   continue;
  34. 	   if (curr&(1ll<<(k+1)) && !(curr&(1ll<<k))) {
  35. 		   ll next = curr - pow2[k];
  36. 		   if( !solve(next) )
  37. 			   ans=true;  
  38. 	   }   
  39.     } 
  40.  
  41.    if( curr < maxn )
  42.    {
  43. 	   done[curr]=true;
  44. 	   return memo2[curr]=ans;
  45.    }
  46.    return memo[curr]=ans;
  47. }                        
  48.  
  49. int main()
  50. {
  51.      pow2[0]=1LL;
  52.  
  53.      for(int i=1;i<=35;i++)
  54.            pow2[i]=pow2[i-1]*2;
  55.  
  56.  
  57.   memset(done , 0, sizeof(done) );
  58.  
  59.  
  60.     int test;
  61.     ll n;
  62.  
  63.     cin>>test;
  64.  
  65.     while( test-- )
  66.     {
  67.          cin>>n;
  68.  
  69.       if( solve(n) )
  70.           cout<<"First Player\n";
  71.        else
  72.            cout<<"Second Player\n";
  73.     }  
  74. 	return 0;
  75. }
Success #stdin #stdout 4.28s 295872KB
comments (?)
stdin
copy 
5
99999999
98765432
87654321
76543210
65432109
stdout
copy 
First Player
First Player
First Player
First Player
Second Player
https://ideone.com/oK0fwy
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!