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. int beauty( ll x )
  19. {
  20.   int ans=0;
  21.  
  22.   for(int i=0;i<35;i++)
  23.         if( x & (1LL<<i) )
  24.           ans++;
  25.  
  26.     return ans;
  27. }    
  28.  
  29. bool solve( ll curr )
  30. {
  31.  
  32.   if( curr < maxn )
  33.    {
  34.       if( done[curr] )
  35.        return memo2[curr];
  36.    }
  37.  else if( memo.count(curr) )
  38.          return memo[curr];
  39.  
  40.  
  41.     bool ans=false;
  42.  
  43.    int ob=beauty(curr); 
  44.  
  45.    for(int k=32;k>=0;k--)
  46.    {   if( pow2[k] >= curr )
  47.         continue;
  48.  
  49.     ll next = curr - pow2[k];
  50.  
  51.       if( beauty( next )==ob )
  52.         { 
  53.           if( !solve(next) )
  54.                ans=true;
  55.  
  56.         }
  57.  
  58.  
  59.     } 
  60.  
  61.    if( curr < maxn )
  62.     {  done[curr]=true;
  63.  
  64.         return memo2[curr]=ans;
  65.      }    
  66.  
  67.   return  memo[curr]=ans;
  68. }                        
  69.  
  70.  
  71.  
  72.  
  73. int main()
  74. {
  75.  
  76.      pow2[0]=1LL;
  77.  
  78.      for(int i=1;i<=35;i++)
  79.            pow2[i]=pow2[i-1]*2;
  80.  
  81.  
  82.   memset(done , 0, sizeof(done) );
  83.  
  84.  
  85.     int test;
  86.     ll n;
  87.  
  88.     cin>>test;
  89.  
  90.     while( test-- )
  91.     {
  92.          cin>>n;
  93.  
  94.       if( solve(n) )
  95.           cout<<"First Player\n";
  96.        else
  97.            cout<<"Second Player\n";
  98.     }  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.      return 0;
  105. }
Time limit exceeded #stdin #stdout 5s 295872KB
comments (?)
stdin
copy 
5
99999999
98765432
87654321
76543210
65432109
54321098
stdout
copy 
First Player
https://ideone.com/bo1Ma2
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!