結果
問題 | No.715 集合と二人ゲーム |
ユーザー |
![]() |
提出日時 | 2018-07-15 13:59:51 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 186 ms / 2,000 ms |
コード長 | 1,366 bytes |
コンパイル時間 | 830 ms |
コンパイル使用メモリ | 92,372 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-11-06 08:03:20 |
合計ジャッジ時間 | 6,998 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 60 |
ソースコード
#include<cstdio>#include<cstring>#include<vector>#include<queue>#include<stack>#include<algorithm>#include<cmath>#include<climits>#include<string>#include<set>#include<unordered_set>#include<numeric>#include<map>#include<iostream>using namespace std;#define rep(i,n) for(int i = 0;i<((int)(n));i++)#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)typedef long long ll;typedef pair<ll, ll> mp;ll mod = 1e9+7;ll inf = 1e18;//WAint main(void){ll n,a[500010],cur=0,grundy[500010],sum=0;grundy[0]=0;grundy[1]=1;grundy[2]=1;reg(i,3,88){unordered_set<ll> s;reg(j,1,(i+1)/2){s.insert(grundy[max(0,j-2)] xor grundy[max(0,i-j-1)]);}rep(j,500010){if(s.count(j)==0){grundy[i]=j;break;}}}reg(i,89,500000){grundy[i]=grundy[i-34];//周期性を利用(実際に見て確かめるしかない)}vector<ll> c;cin>>n;rep(i,n)cin>>a[i];sort(a,a+n);//連続する個数を求めるrep(i,n){if(cur!=0){if(a[i]-a[i-1]<=1){cur++;}else{c.push_back(cur);cur=1;}}else{cur=1;}}c.push_back(cur);rep(i,c.size()){sum = sum xor grundy[c[i]];}if(sum!=0){cout<<"First"<<endl;}else{cout<<"Second"<<endl;}return 0;}