結果
| 問題 | No.3738 Right Hamiltonian |
| コンテスト | |
| ユーザー |
 snuke
|
| 提出日時 | 2026-09-26 08:52:48 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 906 ms / 2,000 ms |
| + 372µs | |
| コード長 | 8,492 bytes |
| 記録 | |
| コンパイル時間 | 2,762 ms |
| コンパイル使用メモリ | 359,752 KB |
| 実行使用メモリ | 90,080 KB |
| 最終ジャッジ日時 | 2026-09-26 08:52:59 |
| 合計ジャッジ時間 | 9,364 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge1_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| 部分点 | 80 % | AC * 38 |
| 満点 | 20 % | AC * 60 |
| 合計 | 4 * 100% = 400 点 |
ソースコード
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep1(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < (t); ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define pob pop_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define newline puts("")
#define vc vector
using namespace std;
template<class T> using vv = vc<vc<T>>;
template<class T> using PQ = priority_queue<T,vc<T>,greater<T>>;
using uint = unsigned; using ull = unsigned long long;
using vi = vc<int>; using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long; using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vv<vl>;
using P = pair<int,int>; using vp = vc<P>; using vvp = vv<P>; using LP = pair<ll,ll>;
int geti(){int x;cin>>x;return x;}
vi pm(int n, int s=0) { vi a(n); iota(rng(a),s); return a;}
template<class T1,class T2>istream& operator>>(istream&i,pair<T1,T2>&v){return i>>v.fi>>v.se;}
template<class T1,class T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v){return o<<v.fi<<","<<v.se;}
template<class T>istream& operator>>(istream&i,vc<T>&v){rep(j,sz(v))i>>v[j];return i;}
template<class T>string join(const T&v,const string&d=""){stringstream s;rep(i,sz(v))(i?s<<d:s)<<v[i];return s.str();}
template<class T>ostream& operator<<(ostream&o,const vc<T>&v){if(sz(v))o<<join(v," ");return o;}
template<class T>ostream& operator<<(ostream&o,const vv<T>&v){for(auto&r:v)o<<r<<'\n';return o;}
template<class T>void vin(vc<T>&a){int n;cin>>n;a=vc<T>(n);cin>>a;}
template<class T>void vin(vv<T>&a){int n,m;cin>>n>>m;a=vv<T>(n,vc<T>(m));cin>>a;}
template<class T1,class T2>void operator--(pair<T1,T2>&a,int){a.fi--;a.se--;}
template<class T1,class T2>void operator++(pair<T1,T2>&a,int){a.fi++;a.se++;}
template<class T>void operator--(vc<T>&a,int){for(T&x:a)x--;}
template<class T>void operator++(vc<T>&a,int){for(T&x:a)x++;}
template<class T1,class T2>pair<T1,T2>operator+(const pair<T1,T2>&a,const pair<T1,T2>&b){return {a.fi+b.fi,a.se+b.se};}
template<class T1,class T2>pair<T1,T2>operator-(const pair<T1,T2>&a,const pair<T1,T2>&b){return {a.fi-b.fi,a.se-b.se};}
template<class T1,class T2>pair<T1,T2>operator*(const pair<T1,T2>&a,const pair<T1,T2>&b){return {a.fi*b.fi,a.se*b.se};}
template<class T>pair<T,T>operator*(const pair<T,T>&a,T b){return {a.fi*b,a.se*b};}
template<class T1,class T2>void operator+=(pair<T1,T2>&a,const pair<T1,T2>&b){a.fi+=b.fi;a.se+=b.se;}
template<class T1,class T2>void operator-=(pair<T1,T2>&a,const pair<T1,T2>&b){a.fi-=b.fi;a.se-=b.se;}
template<class T1,class T2>void operator*=(pair<T1,T2>&a,const pair<T1,T2>&b){a.fi*=b.fi;a.se*=b.se;}
template<class T>void operator*=(pair<T,T>&a,T b){a.fi*=b;a.se*=b;}
template<class T1,class T2>void operator+=(vc<T1>&a,T2 b){for(T1&x:a)x+=b;}
template<class T1,class T2>void operator-=(vc<T1>&a,T2 b){for(T1&x:a)x-=b;}
template<class T1,class T2>void operator*=(vc<T1>&a,T2 b){for(T1&x:a)x*=b;}
template<class T1,class T2>void operator/=(vc<T1>&a,T2 b){for(T1&x:a)x/=b;}
template<class T1,class T2>void operator%=(vc<T1>&a,T2 b){for(T1&x:a)x%=b;}
template<class T>void operator+=(vc<T>&a,const vc<T>&b){a.insert(a.end(),rng(b));}
template<class T1,class T2>bool mins(T1& x,const T2&y){if(y<x){x=y;return true;}else return false;}
template<class T1,class T2>bool maxs(T1& x,const T2&y){if(x<y){x=y;return true;}else return false;}
template<class T>T min(const vc<T>&a){return *min_element(rng(a));}
template<class T>T max(const vc<T>&a){return *max_element(rng(a));}
template<class Tx,class Ty>Tx dup(Tx x, Ty y){return (x+y-1)/y;}
template<class T>ll suma(const vc<T>&a){ll s=0;for(auto&&x:a)s+=x;return s;}
template<class T>ll suma(const vv<T>&a){ll s=0;for(auto&&x:a)s+=suma(x);return s;}
template<class T>void uni(T&a){sort(rng(a));a.erase(unique(rng(a)),a.end());}
template<class T1,class T2>void prepend(vc<T1>&a,const T2&x){a.insert(a.begin(),x);}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { cout<<"-1"<<'\n'; return;}
#define yes { cout<<"Yes"<<'\n'; return;}
#define ye { cout<<"Yes"<<'\n';}
#define no { cout<<"No"<<'\n'; return;}
#define yn {cout<<"Yes"<<'\n';}else{cout<<"No"<<'\n';}
#define rtn(x) { cout<<(x)<<'\n'; return;} // flush!
#define endl '\n'
using vs = vc<string>;
void vin(vs& s){int n,m;cin>>n>>m;s=vs(n);cin>>s;}
template<typename T>void rot(T& a,int i){rotate(a.begin(),a.begin()+(i),a.end());}
void rot(vs& a){int h=sz(a),w=sz(a[0]);vs p(w,string(h,0));swap(a,p);rep(i,h)rep(j,w)a[j][h-1-i]=p[i][j];}
struct Solver {
void solve() {
int h,w;
cin>>h>>w;
vs s(h);
cin>>s;
int tot = 0;
rep(i,h)rep(j,w) if (s[i][j] == '.') tot++;
if (tot == 0) {
rep(i,h)rep(j,w) {
cout<<i+1<<" "<<j+1<<" "<<'L'<<endl;
cout<<0<<endl;
return;
}
}
rep(k,4) {
vvvi d(4,vvi(h,vi(w,-1)));
rep(i,h)rep(j,w) if (s[i][j] == '.') {
d[0][i][j] = d[1][i][j] = 0;
if (i && s[i-1][j] == '.') d[0][i][j] = d[0][i-1][j]+1;
if (j && s[i][j-1] == '.') d[1][i][j] = d[1][i][j-1]+1;
}
drep(i,h)drep(j,w) if (s[i][j] == '.') {
d[2][i][j] = d[3][i][j] = 0;
if (i+1 < h && s[i+1][j] == '.') d[2][i][j] = d[2][i+1][j]+1;
if (j+1 < w && s[i][j+1] == '.') d[3][i][j] = d[3][i][j+1]+1;
}
vi er;
auto fr = [&](int i, int j, int li, int ri, int lj, int rj) {
if (s[i][j] != '.') return -INF;
int res = 1;
int dir = 2;
while (1) {
int lim = 0;
if (dir == 0) lim = i-li;
if (dir == 1) lim = j-lj;
if (dir == 2) lim = ri-i;
if (dir == 3) lim = rj-j;
int e = min(d[dir][i][j],lim);
if (e <= 0) break;
er.pb(e); res += e;
if (dir == 0) i -= e, li = i, lj++;
if (dir == 1) j -= e, lj = j, ri--;
if (dir == 2) i += e, ri = i, rj--;
if (dir == 3) j += e, rj = j, li++;
dir = (dir+3)%4;
}
return res;
};
vi el; P sp; int dir;
auto fl = [&](int i, int j, int li, int ri, int lj, int rj) {
if (s[i][j] != '.') return -INF;
int res = 1;
int k = 0, last = -1;
while (1) {
int lim = 0;
if (k == 0) lim = i-li;
if (k == 1) lim = j-lj;
if (k == 2) lim = ri-i;
if (k == 3) lim = rj-j;
int e = min(d[k][i][j],lim);
if (e <= 0) break;
el.pb(e); res += e; last = k;
if (k == 0) i -= e, li = i, rj--;
if (k == 1) j -= e, lj = j, li++;
if (k == 2) i += e, ri = i, lj++;
if (k == 3) j += e, rj = j, ri--;
k = (k+1)%4;
}
sp = P(i,j); dir = last == -1 ? 0 : last;
return res;
};
int rj = -1, li = 0, ri = 0;
rep(j,w)rep(i,h) if (s[i][j] == '.') rj = j;
rep(i,h) if (s[i][rj] == '.') ri = i;
drep(i,h) if (s[i][rj] == '.') li = i;
rep(ci,h+1) {
if ([&]{
int num = 0;
el = er = vi();
if (!ci) {
num += fr(li,rj, 0,h-1,0,rj);
sp = P(li,rj); dir = 0;
} else if (ci == h) {
num += fl(ri,rj, 0,h-1,0,rj);
} else {
num += fr(ci,rj, ci,h-1,0,rj);
num += fl(ci-1,rj, 0,ci-1,0,rj);
}
if (num != tot) return false;
reverse(rng(el));
string ans;
auto add = [&](vi& es) {
bool fst = true;
for (int e : es) {
string now(e,'F');
if (fst) fst = false; else now[0] = 'R';
ans += now;
}
};
add(el);
if (0 < ci && ci < h) ans += 'F';
add(er);
rep(t,k) {
sp = P(w-1-sp.se,sp.fi);
swap(h,w);
}
dir = (dir+k)%4;
cout<<sp.fi+1<<" "<<sp.se+1<<' '<<("DRUL"[dir])<<endl;
cout<<sz(ans)<<endl;
cout<<ans<<endl;
return true;
}()) return;
}
rot(s); swap(h,w);
}
dame;
}
};
int main() {
cin.tie(nullptr); ios::sync_with_stdio(false);
int ts = 1;
// cin >> ts;
rep1(ti,ts) {
Solver solver;
solver.solve();
}
return 0;
}