結果

問題 No.1315 渦巻洞穴
ユーザー chocoruskchocorusk
提出日時 2020-12-25 23:29:42
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 5,842 bytes
コンパイル時間 1,637 ms
コンパイル使用メモリ 142,188 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-22 17:02:10
合計ジャッジ時間 5,262 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 3 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 3 ms
6,944 KB
testcase_14 AC 3 ms
6,948 KB
testcase_15 AC 3 ms
6,940 KB
testcase_16 AC 3 ms
6,944 KB
testcase_17 AC 3 ms
6,940 KB
testcase_18 AC 3 ms
6,944 KB
testcase_19 AC 3 ms
6,944 KB
testcase_20 AC 3 ms
6,940 KB
testcase_21 AC 3 ms
6,940 KB
testcase_22 AC 3 ms
6,940 KB
testcase_23 AC 4 ms
6,940 KB
testcase_24 AC 3 ms
6,940 KB
testcase_25 AC 3 ms
6,944 KB
testcase_26 AC 4 ms
6,944 KB
testcase_27 AC 4 ms
6,940 KB
testcase_28 AC 4 ms
6,944 KB
testcase_29 AC 4 ms
6,940 KB
testcase_30 AC 3 ms
6,940 KB
testcase_31 AC 4 ms
6,940 KB
testcase_32 AC 3 ms
6,944 KB
testcase_33 AC 4 ms
6,940 KB
testcase_34 AC 4 ms
6,940 KB
testcase_35 AC 3 ms
6,944 KB
testcase_36 AC 4 ms
6,944 KB
testcase_37 AC 4 ms
6,940 KB
testcase_38 AC 3 ms
6,944 KB
testcase_39 AC 3 ms
6,944 KB
testcase_40 AC 3 ms
6,944 KB
testcase_41 AC 3 ms
6,940 KB
testcase_42 AC 3 ms
6,944 KB
testcase_43 AC 4 ms
6,944 KB
testcase_44 AC 4 ms
6,944 KB
testcase_45 AC 3 ms
6,944 KB
testcase_46 AC 3 ms
6,944 KB
testcase_47 AC 3 ms
6,940 KB
testcase_48 AC 3 ms
6,940 KB
testcase_49 AC 4 ms
6,940 KB
testcase_50 AC 4 ms
6,944 KB
testcase_51 AC 3 ms
6,940 KB
testcase_52 AC 4 ms
6,944 KB
testcase_53 AC 4 ms
6,940 KB
testcase_54 AC 4 ms
6,944 KB
testcase_55 AC 3 ms
6,940 KB
testcase_56 AC 3 ms
6,940 KB
testcase_57 AC 4 ms
6,944 KB
testcase_58 AC 3 ms
6,944 KB
testcase_59 AC 3 ms
6,940 KB
testcase_60 AC 3 ms
6,940 KB
testcase_61 AC 3 ms
6,940 KB
testcase_62 AC 3 ms
6,940 KB
testcase_63 AC 3 ms
6,940 KB
testcase_64 AC 3 ms
6,944 KB
testcase_65 AC 3 ms
6,940 KB
testcase_66 AC 2 ms
6,944 KB
testcase_67 AC 3 ms
6,940 KB
testcase_68 AC 3 ms
6,944 KB
testcase_69 AC 3 ms
6,944 KB
testcase_70 AC 2 ms
6,944 KB
testcase_71 AC 3 ms
6,940 KB
testcase_72 AC 3 ms
6,940 KB
testcase_73 AC 3 ms
6,944 KB
testcase_74 AC 3 ms
6,940 KB
testcase_75 AC 2 ms
6,944 KB
testcase_76 AC 2 ms
6,944 KB
testcase_77 AC 3 ms
6,940 KB
testcase_78 AC 3 ms
6,944 KB
testcase_79 AC 4 ms
6,940 KB
testcase_80 AC 4 ms
6,940 KB
testcase_81 AC 3 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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});
      |                         ^

ソースコード

diff # 

#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;
}
0