#787040 (C++14) No.1576 織姫と彦星

• 問題: No.1576 織姫と彦星
• ユーザー: TKTYI
• 提出日時: 2022-08-11 15:04:55
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 78 ms / 2,000 ms
• コード長: 2,023 bytes
• コンパイル時間: 3,887 ms
• コンパイル使用メモリ: 231,932 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-21 21:46:40
• 合計ジャッジ時間: 6,388 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	8 ms; 5,376 KB
testcase_08	AC	4 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	36 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	21 ms; 5,376 KB
testcase_13	AC	19 ms; 5,376 KB
testcase_14	AC	35 ms; 5,376 KB
testcase_15	AC	29 ms; 5,376 KB
testcase_16	AC	15 ms; 5,376 KB
testcase_17	AC	23 ms; 5,376 KB
testcase_18	AC	7 ms; 5,376 KB
testcase_19	AC	14 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	26 ms; 5,376 KB
testcase_22	AC	6 ms; 5,376 KB
testcase_23	AC	3 ms; 5,376 KB
testcase_24	AC	5 ms; 5,376 KB
testcase_25	AC	20 ms; 5,376 KB
testcase_26	AC	18 ms; 5,376 KB
testcase_27	AC	2 ms; 5,376 KB
testcase_28	AC	21 ms; 5,376 KB
testcase_29	AC	19 ms; 5,376 KB
testcase_30	AC	2 ms; 5,376 KB
testcase_31	AC	13 ms; 5,376 KB
testcase_32	AC	22 ms; 5,376 KB
testcase_33	AC	67 ms; 5,376 KB
testcase_34	AC	2 ms; 5,376 KB
testcase_35	AC	21 ms; 5,376 KB
testcase_36	AC	5 ms; 5,376 KB
testcase_37	AC	68 ms; 5,376 KB
testcase_38	AC	29 ms; 5,376 KB
testcase_39	AC	23 ms; 5,376 KB
testcase_40	AC	16 ms; 5,376 KB
testcase_41	AC	21 ms; 5,376 KB
testcase_42	AC	3 ms; 5,376 KB
testcase_43	AC	6 ms; 5,376 KB
testcase_44	AC	78 ms; 5,376 KB
testcase_45	AC	11 ms; 5,376 KB
testcase_46	AC	49 ms; 5,376 KB
testcase_47	AC	2 ms; 5,376 KB
testcase_48	AC	25 ms; 5,376 KB
testcase_49	AC	22 ms; 5,376 KB
testcase_50	AC	3 ms; 5,376 KB
testcase_51	AC	3 ms; 5,376 KB
testcase_52	AC	5 ms; 5,376 KB
testcase_53	AC	44 ms; 5,376 KB
testcase_54	AC	24 ms; 5,376 KB
testcase_55	AC	26 ms; 5,376 KB
testcase_56	AC	27 ms; 5,376 KB
testcase_57	AC	2 ms; 5,376 KB
testcase_58	AC	9 ms; 5,376 KB

ソースコード

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long int ll;
typedef long double ld;
#define FOR(i,l,r) for(ll i=l;i<r;i++)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,l,r) for(ll i=r-1;i>=l;i--)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define PA pair<ll,ll>
#define F first
#define S second
#define BS(A,x) binary_search(ALL(A),x)
#define LB(A,x) (ll)(lower_bound(ALL(A),x)-A.begin())
#define UB(A,x) (ll)(upper_bound(ALL(A),x)-A.begin())
#define COU(A,x) (UB(A,x)-LB(A,x))
#define sz(c) ((ll)(c).size())
//#include<boost/multiprecision/cpp_int.hpp>
//namespace mp=boost::multiprecision;
//using Bint=mp::cpp_int;
template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<typename T1,typename T2>ostream&operator<<(ostream&os,pair<T1,T2>&p){os<<p.F<<" "<<p.S;return os;}
template<typename T1,typename T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.F>>p.S;return is;}
template<typename T>ostream&operator<<(ostream&os,vector<T>&v){REP(i,sz(v))os<<v[i]<<(i+1!=sz(v)?" ":"");return os;}
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;}
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;}
ld dist(ld x1,ld y1,ld x2,ld y2){return sqrtl((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
//using mint=modint1000000007;
using mint=modint998244353;
//const ll mod=1000000007;
const ll mod=998244353;
//using mint=modint;
ostream&operator<<(ostream&os,mint&a){os<<a.val();return os;}
int main(){
  ll N;cin>>N;
  vector<ll>X(N+2);
  cin>>X[0]>>X[N+1];
  FOR(i,1,N+1)cin>>X[i];
  vector<ll>D(N+2,1e18);
  D[0]=0;
  queue<ll>Q;
  Q.emplace(0);
  while(sz(Q)){
    ll v=Q.front();Q.pop();
    REP(u,N+2){
        ll c=0;
        REP(i,30)if((X[v]>>i)%2!=(X[u]>>i)%2)c++;
        if(c<=1&&chmin(D[u],D[v]+1))Q.emplace(u);
    }
  }
  if(D[N+1]==1e18)D[N+1]=0;
  cout<<D[N+1]-1<<endl;
  return 0;
}