結果
| 問題 | No.1315 渦巻洞穴 |
| ユーザー |
 milanis48663220
|
| 提出日時 | 2020-12-12 22:18:10 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 6 ms / 2,000 ms |
| コード長 | 4,820 bytes |
| コンパイル時間 | 1,360 ms |
| コンパイル使用メモリ | 110,112 KB |
| 最終ジャッジ日時 | 2025-01-16 23:05:36 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 79 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <set>#include <map>#include <cassert>#include <cmath>#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }using namespace std;typedef long long ll;struct point{ll x, y;};const double eps = 0.01;void validate(string s);ll right_up(ll k){ return (2*k-1)*(2*k-1)+(2*k); }ll left_up(ll k){ return (2*k)*(2*k)+1; }ll left_bottom(ll k){ return (2*k)*(2*k)+2*k+1; }ll right_bottom(ll k){ return (2*k+1)*(2*k+1); }ll sqrt_ll(ll n){ll ans = (ll)(sqrt(n)+eps);if(ans*ans > n) ans--;return ans;}ll to_cycle(ll n){ll s = sqrt_ll(n);if(s%2 == 0) s--;if(s*s == n){return (s+1)/2-1;}return (s+3)/2-1;}point to_cood(ll n){ll k = to_cycle(n);ll x = -1, y = -1;if(n <= right_up(k)){x = k, y = k-(right_up(k)-n);}else if(n <= left_up(k)){x = -k+(left_up(k)-n), y = k;}else if(n <= left_bottom(k)){x = -k, y = -k+(left_bottom(k)-n);}else{x = k-(right_bottom(k)-n), y = -k;}return (point){x, y};}ll to_number(point p){ll k = max(abs(p.x), abs(p.y));if(p.x == k){return right_up(k)-(k-p.y);}else if(p.y == k){return left_up(k)-(p.x+k);}else if(p.x == -k){return left_bottom(k)-(p.y+k);}else{return right_bottom(k)-(k-p.x);}}ll dist(point p1, point p2){return abs(p1.x-p2.x)+abs(p1.y-p2.y);}ll s, t;ll x, y;ll sx, sy, tx, ty;vector<ll> vx, vy;void go_up(){y++;vx.push_back(x);vy.push_back(y);}void go_down(){y--;vx.push_back(x);vy.push_back(y);}void go_left(){x--;vx.push_back(x);vy.push_back(y);}void go_right(){x++;vx.push_back(x);vy.push_back(y);}void solve_odd(){while(x != tx){if(x < tx) go_right();else go_left();}while(y != ty){if(y < ty) go_up();else go_down();}ll sz = vx.size();string ans;for(ll i = 0; i < sz-1; i++){if(i%2 == 0){if(vx[i+1] == vx[i]+1) ans += "RLR";if(vx[i+1] == vx[i]-1) ans += "LRL";if(vy[i+1] == vy[i]+1) ans += "UDU";if(vy[i+1] == vy[i]-1) ans += "DUD";}else{if(vx[i+1] == vx[i]+1) ans += "R";if(vx[i+1] == vx[i]-1) ans += "L";if(vy[i+1] == vy[i]+1) ans += "U";if(vy[i+1] == vy[i]-1) ans += "D";}}assert(ans.size() <= 200000);cout << 0 << endl;cout << ans.size() << endl;cout << ans << endl;validate(ans);}void solve_even(){ll u = s^t;auto pu = to_cood(u);ll ux = pu.x, uy = pu.y;while(x != ux){if(x < ux) go_right();else go_left();}while(y != uy){if(y < uy) go_up();else go_down();}while(x != tx){if(x < tx) go_right();else go_left();}while(y != ty){if(y < ty) go_up();else go_down();}ll sz = vx.size();ll i = 0;string ans;for(ll j = 0; j < sz-1; j++){if(i%2 == 1){if(vx[j+1] == vx[j]+1) ans += "RLR";if(vx[j+1] == vx[j]-1) ans += "LRL";if(vy[j+1] == vy[j]+1) ans += "UDU";if(vy[j+1] == vy[j]-1) ans += "DUD";}else{if(vx[j+1] == vx[j]+1) ans += "R";if(vx[j+1] == vx[j]-1) ans += "L";if(vy[j+1] == vy[j]+1) ans += "U";if(vy[j+1] == vy[j]-1) ans += "D";}if(vx[j+1] != ux || vy[j+1] != uy) i++;}assert(ans.size() <= 200000);cout << 0 << endl;cout << ans.size() << endl;cout << ans << endl;validate(ans);}void validate(string d){auto ps = to_cood(s);int x = ps.x, y = ps.y;int ans = to_number((point){x, y});for(char c : d){if(c == 'U') y++;if(c == 'D') y--;if(c == 'L') x--;if(c == 'R') x++;ans ^= to_number((point){x, y});}// assert(ans == 0);}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;cin >> s >> t;auto ps = to_cood(s);auto pt = to_cood(t);x = ps.x, y = ps.y;sx = ps.x, sy = ps.y;tx = pt.x, ty = pt.y;vx.push_back(sx);vy.push_back(sy);if(dist(ps, pt)%2 == 0){solve_even();}else{solve_odd();}}