結果
問題 |
No.1315 渦巻洞穴
|
ユーザー |
![]() |
提出日時 | 2020-12-25 23:29:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 5,842 bytes |
コンパイル時間 | 1,422 ms |
コンパイル使用メモリ | 136,844 KB |
最終ジャッジ日時 | 2025-01-17 07:25:52 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 79 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:168:25: warning: narrowing conversion of ‘v’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing] 168 | que.push({{x1, y1}, v}); | ^
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #define popcount __builtin_popcount using namespace std; typedef long long ll; typedef pair<ll, ll> P; int a[7][7]={{37,36,35,34,33,32,31},{38,17,16,15,14,13,30},{39,18,5,4,3,12,29},{40,19,6,1,2,11,28},{41,20,7,8,9,10,27},{42,21,22,23,24,25,26},{43,44,45,46,47,48,49}}; ll calc(ll x, ll y){ ll c=max(abs(x), abs(y)); ll s=(2*c+1)*(2*c+1); if(y==-c) return s-(c-x); else if(x==-c) return s-2*c-(y+c); else if(y==c) return s-4*c-(x+c); else return s-6*c-(c-y); } P calc2(ll v){ if(v==1) return P(0ll, 0ll); ll l=0, r=1e5; while(r-l>1){ ll m=(l+r)/2; if((2*m+1)*(2*m+1)>=v) r=m; else l=m; } ll s=(2*r+1)*(2*r+1); if(s-v<=2*r) return P(r-(s-v), -r); else if(s-v<=4*r) return P(-r, -r+(s-2*r-v)); else if(s-v<=6*r) return P(-r+(s-4*r-v), r); else return P(r, r-(s-6*r-v)); } string s0="RLUD"; string sr="LRDU"; int main() { ll s, t; cin>>s>>t; //s=1000000000; P p1=calc2(s); ll x1=p1.first, y1=p1.second; ll v=s, w=t; int dx[4]={1, -1, 0, 0}, dy[4]={0, 0, 1, -1}; string ans, ansr; int sum1=0; while(v>9){ for(int k=0; k<4; k++){ if(v&1){ ll x2=x1+dx[k], y2=y1+dy[k]; if(calc(x2, y2)==v-1){ ll mn=1e18; int lmn=-1; for(int l=0; l<4; l++){ ll x3=x2+dx[l], y3=y2+dy[l]; ll c3=calc(x3, y3); if(c3==v) continue; if(c3<mn){ mn=c3; lmn=l; } } v=mn; x1=x2+dx[lmn], y1=y2+dy[lmn]; ans+=s0[k];ans+=s0[lmn]; sum1^=1; } }else{ ll x2=x1+dx[k], y2=y1+dy[k]; if(calc(x2, y2)==v+1){ ll mn=1e18; int lmn=-1; for(int l=0; l<4; l++){ ll x3=x2+dx[l], y3=y2+dy[l]; ll c3=calc(x3, y3); if(c3==v) continue; if(c3<mn){ mn=c3; lmn=l; } } v=mn; x1=x2+dx[lmn], y1=y2+dy[lmn]; ans+=s0[k];ans+=s0[lmn]; sum1^=1; } } } } P p2=calc2(t); ll x11=p2.first, y11=p2.second; while(w>9){ for(int k=0; k<4; k++){ if(w&1){ ll x2=x11+dx[k], y2=y11+dy[k]; if(calc(x2, y2)==w-1){ ll mn=1e18; int lmn=-1; for(int l=0; l<4; l++){ ll x3=x2+dx[l], y3=y2+dy[l]; ll c3=calc(x3, y3); if(c3==w) continue; if(c3<mn){ mn=c3; lmn=l; } } w=mn; x11=x2+dx[lmn], y11=y2+dy[lmn]; ansr+=sr[k];ansr+=sr[lmn]; sum1^=1; } }else{ ll x2=x11+dx[k], y2=y11+dy[k]; if(calc(x2, y2)==w+1){ ll mn=1e18; int lmn=-1; for(int l=0; l<4; l++){ ll x3=x2+dx[l], y3=y2+dy[l]; ll c3=calc(x3, y3); if(c3==w) continue; if(c3<mn){ mn=c3; lmn=l; } } w=mn; x11=x2+dx[lmn], y11=y2+dy[lmn]; ansr+=sr[k];ansr+=sr[lmn]; sum1^=1; } } } } reverse(ansr.begin(), ansr.end()); using Pi=pair<P, int>; using PP=pair<P, P>; const int INF=1e9; int d[7][7][64]; PP pr[7][7][64]; for(int i=0; i<7; i++){ for(int j=0; j<7; j++){ for(int k=0; k<64; k++){ d[i][j][k]=INF; } } } queue<Pi> que; que.push({{x1, y1}, v}); d[3-y1][3+x1][v]=0; while(!que.empty()){ Pi p=que.front(); que.pop(); int x=p.first.first, y=p.first.second, sum=p.second; for(int k=0; k<4; k++){ int xn=x+dx[k], yn=y+dy[k]; if(abs(xn)>3 || abs(yn)>3) continue; int sum1=(sum^a[3-yn][3+xn]); if(d[3-yn][3+xn][sum1]>d[3-y][3+x][sum]+1){ d[3-yn][3+xn][sum1]=d[3-y][3+x][sum]+1; pr[3-yn][3+xn][sum1]=PP(P(3-y, 3+x), P(sum, k)); que.push({{xn, yn}, sum1}); } } } assert(d[3-y11][3+x11][sum1]<INF); string ansm; ll sum0=sum1; while(y11!=y1 || x11!=x1 || sum0!=v){ PP pp=pr[3-y11][3+x11][sum0]; y11=3-pp.first.first; x11=pp.first.second-3; sum0=pp.second.first; ansm+=s0[pp.second.second]; } reverse(ansm.begin(), ansm.end()); ans+=ansm; ans+=ansr; cout<<0<<endl; cout<<ans.size()<<endl; cout<<ans<<endl; return 0; }