結果
問題 | No.1152 10億ゲーム |
ユーザー | beet |
提出日時 | 2020-08-07 23:19:20 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,177 bytes |
コンパイル時間 | 2,153 ms |
コンパイル使用メモリ | 209,812 KB |
実行使用メモリ | 39,872 KB |
平均クエリ数 | 0.08 |
最終ジャッジ日時 | 2023-09-24 05:02:29 |
合計ジャッジ時間 | 6,110 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | TLE | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
testcase_49 | -- | - |
ソースコード
#include <bits/stdc++.h> using namespace std; using Int = long long; const char newl = '\n'; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);} template<typename T=int> vector<T> read(size_t n){ vector<T> ts(n); for(size_t i=0;i<n;i++) cin>>ts[i]; return ts; } template<typename T> struct Dijkstra{ struct Edge{ int to; T cost; Edge(int to,T cost):to(to),cost(cost){} bool operator<(const Edge &o)const{return cost>o.cost;} }; vector< vector<Edge> > G; vector<T> ds; vector<int> bs; Dijkstra(int n):G(n){} void add_edge(int u,int v,T c){ G[u].emplace_back(v,c); } void build(int s){ int n=G.size(); ds.assign(n,numeric_limits<T>::max()); bs.assign(n,-1); priority_queue<Edge> pq; ds[s]=0; pq.emplace(s,ds[s]); while(!pq.empty()){ auto p=pq.top();pq.pop(); int v=p.to; if(ds[v]<p.cost) continue; for(auto e:G[v]){ if(ds[e.to]>ds[v]+e.cost){ ds[e.to]=ds[v]+e.cost; bs[e.to]=v; pq.emplace(e.to,ds[e.to]); } } } } T operator[](int k){return ds[k];} vector<int> restore(int to){ vector<int> res; if(bs[to]<0) return res; while(~to) res.emplace_back(to),to=bs[to]; reverse(res.begin(),res.end()); return res; } }; //INSERT ABOVE HERE using P = pair<int, int>; P pos(int x){ int r=0,c=0; while(x%2==0) r++,x/=2; while(x%5==0) c++,x/=5; return P(r,c); } int dr[]={0,0,1,-1}; int dc[]={1,-1,0,0}; int in(int r,int c){ return 0<=r and r<10 and 0<=c and c<10; } int idx(int k,int r1,int c1,int r2,int c2){ return (((k*10+r1)*10+c1)*10+r2)*10+c2; } int val(int r,int c){ int x=1; for(int i=0;i<r;i++) x*=2; for(int j=0;j<c;j++) x*=5; return x; } signed main(){ int x1,x2; cin>>x1>>x2; Dijkstra<int> G(20001); int S=20000; vector<int> ss; for(int r1=0;r1<10;r1++){ for(int c1=0;c1<10;c1++){ G.add_edge(S,idx(0,r1,c1,r1,c1),0); G.add_edge(S,idx(1,r1,c1,r1,c1),0); for(int r2=0;r2<10;r2++){ for(int c2=0;c2<10;c2++){ G.add_edge(idx(0,r1,c1,r2,c2),idx(1,r1,c1,r2,c2),1); for(int k=0;k<4;k++){ int nr=r1+dr[k],nc=c1+dc[k]; if(!in(nr,nc)) continue; G.add_edge(idx(1,nr,nc,r2,c2),idx(0,r1,c1,r2,c2),1); } for(int k=0;k<4;k++){ int nr=r2+dr[k],nc=c2+dc[k]; if(!in(nr,nc)) continue; G.add_edge(idx(1,r1,c1,r2,c2),idx(0,r1,c1,nr,nc),0); } } } } } G.build(S); while(1){ auto [r1,c1]=pos(x1); auto [r2,c2]=pos(x2); cout<<G[idx(0,r1,c1,r2,c2)]<<endl; for(int k=0;k<4;k++){ int nr=r1+dr[k],nc=c1+dc[k]; if(!in(nr,nc)) continue; if(val(nr,nc)==x2){ cout<<x2<<endl; return 0; } if(G[idx(1,nr,nc,r2,c2)]<G[idx(0,r1,c1,r2,c2)]){ x1=val(nr,nc); cout<<x1<<endl; break; } } cin>>x2; if(x1==x2) return 0; } return 0; }