結果
| 問題 | No.1315 渦巻洞穴 |
| ユーザー |
 tempura_pp
|
| 提出日時 | 2020-12-01 03:13:56 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 21 ms / 2,000 ms |
| コード長 | 6,068 bytes |
| コンパイル時間 | 2,020 ms |
| コンパイル使用メモリ | 125,780 KB |
| 最終ジャッジ日時 | 2025-01-16 10:58:19 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 79 |
ソースコード
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
constexpr int inf=1e9+7;
constexpr ll longinf=1LL<<60 ;
constexpr ll mod=1e9+7 ;
vector<int> square;
pair<int,int> get(int n){
if(n == 1)return {0, 0};
int idx = lower_bound(square.begin(),square.end(),n)-square.begin();
int len = (square[idx]-square[idx-1])/4;
n -= square[idx-1];
if(n<=len){
return {idx, -idx+n};
} else if(n<=2*len){
return {idx-(n-len),idx};
} else if(n<=3*len){
return {-idx, idx-(n-2*len)};
} else {
return {-idx+(n-3*len),-idx};
}
}
string root(vector<int> ansx, vector<int> ansy){
string res = "";
int n=ansx.size();
rep(i,n-1){
if(ansx[i]<ansx[i+1])res+='R';
if(ansx[i]>ansx[i+1])res+='L';
if(ansy[i]<ansy[i+1])res+='U';
if(ansy[i]>ansy[i+1])res+='D';
}
return res;
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int v = 1;
while(v*v<=2*inf){
square.push_back(v*v);
v+=2;
}
int s, t;
cin>>s>>t;
auto st = get(s), en = get(t);
int sx = st.first, sy = st.second;
int ex = en.first, ey = en.second;
int dist = abs(ex-sx)+abs(ey-sy);
if(dist%2 == 1){
int cx = sx, cy = sy;
vector<int> xs, ys;
xs.push_back(cx); ys.push_back(cy);
while(cx!=ex||cy!=ey){
if(cx!=ex){
if(cx<ex)++cx;
else --cx;
} else {
if(cy<ey)++cy;
else --cy;
}
xs.push_back(cx);ys.push_back(cy);
}
assert(xs.size()%2==0);
vector<int> ansx, ansy;
int n = xs.size()/2;
rep(i,n){
rep(j,2){
ansx.push_back(xs[2*i]);ansy.push_back(ys[2*i]);
ansx.push_back(xs[2*i+1]);ansy.push_back(ys[2*i+1]);
}
}
string ans = root(ansx, ansy);
cout<<0<<endl;
cout<<ans.size()<<endl;
cout<<ans<<endl;
} else if((abs(sx)+abs(sy))%2 == 0){
vector<int> ansx, ansy;
{
int cx = sx, cy = sy;
vector<int> xs, ys;
xs.push_back(cx); ys.push_back(cy);
int tx = 0, ty = 1;
while(cx!=tx||cy!=ty){
if(cx!=tx){
if(cx<tx)++cx;
else --cx;
} else {
if(cy<ty)++cy;
else --cy;
}
xs.push_back(cx);ys.push_back(cy);
}
assert(xs.size()%2==0);
int n = xs.size()/2;
rep(i,n){
rep(j,2){
ansx.push_back(xs[2*i]);ansy.push_back(ys[2*i]);
ansx.push_back(xs[2*i+1]);ansy.push_back(ys[2*i+1]);
}
}
}
ansx.push_back(0);ansy.push_back(0);
ansx.push_back(1);ansy.push_back(0);
ansx.push_back(1);ansy.push_back(1);
{
int cx = 0, cy = 1;
vector<int> xs, ys;
xs.push_back(cx); ys.push_back(cy);
while(cx!=ex||cy!=ey){
if(cx!=ex){
if(cx<ex)++cx;
else --cx;
} else {
if(cy<ey)++cy;
else --cy;
}
xs.push_back(cx);ys.push_back(cy);
}
assert(xs.size()%2==0);
int n = xs.size()/2;
rep(i,n){
rep(j,2){
ansx.push_back(xs[2*i]);ansy.push_back(ys[2*i]);
ansx.push_back(xs[2*i+1]);ansy.push_back(ys[2*i+1]);
}
}
}
string ans = root(ansx, ansy);
cout<<0<<endl;
cout<<ans.size()<<endl;
cout<<ans<<endl;
} else {
vector<int> ansx, ansy;
{
int cx = sx, cy = sy;
vector<int> xs, ys;
xs.push_back(cx); ys.push_back(cy);
int tx = 1, ty = 1;
while(cx!=tx||cy!=ty){
if(cx!=tx){
if(cx<tx)++cx;
else --cx;
} else {
if(cy<ty)++cy;
else --cy;
}
xs.push_back(cx);ys.push_back(cy);
}
assert(xs.size()%2==0);
int n = xs.size()/2;
rep(i,n){
rep(j,2){
ansx.push_back(xs[2*i]);ansy.push_back(ys[2*i]);
ansx.push_back(xs[2*i+1]);ansy.push_back(ys[2*i+1]);
}
}
}
ansx.push_back(1);ansy.push_back(0);
ansx.push_back(0);ansy.push_back(0);
ansx.push_back(-1);ansy.push_back(0);
ansx.push_back(0);ansy.push_back(0);
ansx.push_back(0);ansy.push_back(1);
{
int cx = 1, cy = 1;
vector<int> xs, ys;
xs.push_back(cx); ys.push_back(cy);
while(cx!=ex||cy!=ey){
if(cx!=ex){
if(cx<ex)++cx;
else --cx;
} else {
if(cy<ey)++cy;
else --cy;
}
xs.push_back(cx);ys.push_back(cy);
}
assert(xs.size()%2==0);
int n = xs.size()/2;
rep(i,n){
rep(j,2){
ansx.push_back(xs[2*i]);ansy.push_back(ys[2*i]);
ansx.push_back(xs[2*i+1]);ansy.push_back(ys[2*i+1]);
}
}
}
string ans = root(ansx, ansy);
cout<<0<<endl;
cout<<ans.size()<<endl;
cout<<ans<<endl;
}
return 0;
}