結果
| 問題 |
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_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;
}