結果
| 問題 | No.1315 渦巻洞穴 |
| ユーザー |
 chocorusk
|
| 提出日時 | 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_popcountusing 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;}