結果
問題 | No.5015 Escape from Labyrinth |
ユーザー |
![]() |
提出日時 | 2023-04-23 18:15:01 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 2,875 ms / 3,000 ms |
コード長 | 14,975 bytes |
コンパイル時間 | 2,795 ms |
コンパイル使用メモリ | 115,976 KB |
実行使用メモリ | 157,052 KB |
スコア | 71,490 |
最終ジャッジ日時 | 2023-04-23 18:20:00 |
合計ジャッジ時間 | 297,775 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;using System.Collections;using System.Collections.Specialized;using System.Linq;using System.Text;using System.Text.RegularExpressions;using System.IO;using System.Reflection;using static System.Math;using System.Numerics;using System.Threading;using System.Runtime.CompilerServices;using System.Diagnostics;using System.Runtime.Remoting.Messaging;using System.Runtime.ExceptionServices;using nint=System.Int64;static class Program {const long inf = long.MaxValue>>1;const int mod = 998244353;static Sc sc = new Sc();static void Main() {Pt pt = new Pt(Solve);pt.Sm();}static void Solve(Pt pt) {var (n, d, h)=sc.Tp3<int>();DateTime st = DateTime.Now;var state = new State(sc,d);while((DateTime.Now-st).TotalMilliseconds<2750) {state.Ex();}pt.W(state.Output());}}public class Nd:IComparable {public int ope;public int pt;public long ef;public Nd pr;public List<Nd> cl;public int nei, dest;public bool bn;public Nd() {bn=true;pt=0;ef=0;ope=-1;}public Nd(Nd pr,int ope,int p,long e) {this.pr=pr;this.ope=ope;pt=p;ef=e;}public void Us() {if(pr.cl==null) pr.cl=new List<Nd>();dest=pr.cl.Count;nei=pr.cl.Count;pr.cl.Add(this);}public int CompareTo(object obj) {Nd nd = (Nd)obj;if(nd.ef>ef) { return 1; }else if(nd.ef<ef) { return -1; }else { return 0; }}}public class State {const int inf = int.MaxValue>>1;public static int[] hy = new int[] { -1,0,1,0 };public static int[] hx = new int[] { 0,1,0,-1 };public int[] hd;const string ht = "URDL";public string[] sa;public long[][] eb0, eb1, eb2, eb3;public int[][] ba;public ulong[][] xan, xaj;public int[][][] ca;const int n = 60, ml = 1501;public StringBuilder sb;private Nd root;public Nd maxnd;public int ny, nx, nh, nj, t;public int iskey = 0;public Pq<Nd>[] pq;private Nd nnd;public ulong xhs;private HashSet<ulong>[] hs;public State(Sc sc,int d) {sa=new string[n+2];hd=new int[] { 0,d };nh=1500;sa[0]=sa[n+1]=new string('#',n+2);eb0=new long[n+2][];eb1=new long[n+2][];eb2=new long[n+2][];eb3=new long[n+2][];ba=new int[n+2][];ca=new int[2][][];ca[0]=new int[n+2][];ca[1]=new int[n+2][];xan=new ulong[n+1][];xaj=new ulong[n+1][];var qu = new Queue<(int d, int b, int y, int x)>();for(int i = 1;i<=n;i++) {sa[i]="#"+sc.S+"#";eb0[i]=new long[n+2];eb1[i]=new long[n+2];eb2[i]=new long[n+2];eb3[i]=new long[n+2];ba[i]=new int[n+2];ca[0][i]=new int[n+2];ca[1][i]=new int[n+2];ca[0][i][0]=ca[0][i][n+1]=inf;ca[1][i][0]=ca[1][i][n+1]=inf;xan[i]=new ulong[n+1];xaj[i]=new ulong[n+1];for(int j = 1;j<=n;j++) {xan[i][j]=Xs();xaj[i][j]=Xs();ca[0][i][j]=ca[1][i][j]=inf;if(sa[i][j]=='S') {ny=i;nx=j;ba[i][j]=1;}else if(sa[i][j]=='G') {qu.Enqueue((0, 1, i, j));ca[1][i][j]=0;}}}while(qu.Count>0) {var e = qu.Dequeue();for(int i = 0;i<4;i++) {int iy = e.y+hy[i];int ix = e.x+hx[i];if(Ps(iy,ix)) { continue; }int bb = sa[e.y][e.x]=='K' ? 0 : e.b;if(ca[bb][iy][ix]!=inf) { continue; }qu.Enqueue((e.d+1, bb, iy, ix));ca[bb][iy][ix]=e.d+1;}}var bi = new long[6];for(int i = 2;i<=5;i++) {for(int j = 0;j<n;j+=i) {bi[i]|=1L<<j;}}var q = sc.I;for(int i = 0;i<q;i++) {var e = sc.Ia;e[0]++;e[1]++;for(int j = e[0]+1;j<=n;j++) {if(Ps(j,e[1])) break;eb0[j][e[1]]|=bi[e[2]];}for(int j = e[0]-1;j>0;j--) {if(Ps(j,e[1])) break;eb1[j][e[1]]|=bi[e[2]];}for(int j = e[1]+1;j<=n;j++) {if(Ps(e[0],j)) break;eb2[e[0]][j]|=bi[e[2]];}for(int j = e[1]-1;j>0;j--) {if(Ps(e[0],j)) break;eb3[e[0]][j]|=bi[e[2]];}}root=new Nd();maxnd=root;nnd=root;hs=new HashSet<ulong>[ml];pq=new Pq<Nd>[ml];for(int i = 0;i<pq.Length;i++) {pq[i]=new Pq<Nd>(32,true);hs[i]=new HashSet<ulong>();}pq[nh].Push(root);}static ulong hsx = 15733141579192332639, hsy = 2335109221169850231, hsz = 11649577722817784940, hsw = (ulong)DateTime.Now.Ticks;public ulong Xs() {ulong t = hsx^(hsx<<11); hsx=hsy; hsy=hsz; hsz=hsw;return hsw=hsw^(hsw>>19)^t^(t>>8);}public void Ex() {for(int i = 1500;i>0;i--) {if(pq[i].cnt==0) continue;var nd = pq[i].Dequeue;if (nd.pr!=null) nd.Us();var lca = nd;while(!lca.bn) {lca.pr.nei=lca.dest;lca=lca.pr;}while(nnd!=lca) {nnd.bn=false;Back(nnd.ope);nnd=nnd.pr;}while(nnd!=nd) {nnd=nnd.cl[nnd.nei];Step(nnd.ope);nnd.bn=true;}for(int j = 0;j<4;j++) {var iy = ny+hy[j];var ix = nx+hx[j];if(Ps(iy,ix)) { continue; }int kh = nh-Dg(iy,ix,t+1)-1;if(kh<1) continue;var hsk = xhs^xan[iy][ix]^(sa[iy][ix]=='J'&&ba[iy][ix]==0 ? xaj[iy][ix] : 0);if(hs[kh].Contains(hsk)) continue;hs[kh].Add(hsk);int bb = sa[iy][ix]=='K' ? 1 : iskey;int kj = nj+(sa[iy][ix]=='J'&&ba[iy][ix]==0 ? 1 : 0);var kp = Fef(kh,kj,iy,ix,bb);var ndk = new Nd(nd,j,kj,kp);pq[kh].Push(ndk);if(sa[iy][ix]=='G'&&ndk.pt>maxnd.pt) {maxnd=ndk;}}}}public bool Ps(int y,int x) { return sa[y][x]=='#'||sa[y][x]=='E'; }public int Dg(int y,int x,int t) {t%=60;return hd[(eb0[y][x]>>t)&1]+hd[(eb1[y][x]>>t)&1]+hd[(eb2[y][x]>>t)&1]+hd[(eb3[y][x]>>t)&1];}public long Fef(int kh,int kj,int ky,int kx,int kk) { return (1500L-kh)*(1500L-kh)*-ca[kk][ky][kx]+kj*1000000L; }private void Step(int ope) {t++;ny+=hy[ope];nx+=hx[ope];if(sa[ny][nx]=='K'&&ba[ny][nx]==0) iskey=1;if(sa[ny][nx]=='J'&&ba[ny][nx]==0) {nj++;xhs^=xaj[ny][nx];}nh-=Dg(ny,nx,t)+1;ba[ny][nx]++;}private void Back(int ope) {ba[ny][nx]--;nh+=Dg(ny,nx,t)+1;if(sa[ny][nx]=='J'&&ba[ny][nx]==0) {nj--;xhs^=xaj[ny][nx];}if(sa[ny][nx]=='K'&&ba[ny][nx]==0) iskey=0;ny-=hy[ope];nx-=hx[ope];t--;}private string Out(int ope) {return "M "+ht[ope]+"\n";}public string Output() {var sa = new List<string>();while(maxnd.ope!=-1) {sa.Add(Out(maxnd.ope));maxnd=maxnd.pr;}return string.Join("",sa.ToArray().Reverse().ToArray());}}public class Dt<T>:IComparable {public nint n;public T d;public static implicit operator Dt<T>((nint, T) e) { return new Dt<T>(e.Item1,e.Item2); }public Dt(nint n,T d) { this.n=n; this.d=d; }public int CompareTo(object obj) {Dt<T> mymo = (Dt<T>)obj;if(mymo.n>n) { return -1; }else if(mymo.n<n) { return 1; }else { return 0; }}public override string ToString() => "d:"+d.ToString()+" n:"+n.ToString();}public class Pq<T> where T : IComparable {private T[] he;public int cnt = 0, max = 0;private Func<T,T,int> compare;public Pq(int max,bool mm) {this.max=max;he=new T[max];if(mm) { compare=Ao; }else { compare=Do; }}public void Push(T x) {if(cnt==max) { Extend(); }int j = cnt;while(j!=0&&compare(x,he[(j-1)>>1])>0) { he[j]=he[(j-1)>>1]; j=(j-1)>>1; }he[j]=x;cnt++;}public void Pop() {cnt--;T r = he[cnt];int j = 0;while(true) {if(j*2+1<cnt) {if(compare(he[j*2+1],he[j*2+2])>0) { j=j*2+1; }else { j=j*2+2; }}else if(j*2<cnt) { j=j*2+1; }else { break; }if(compare(he[j],r)<=0) { j=(j-1)>>1; break; }he[(j-1)>>1]=he[j];}he[j]=r;}private int Ao(T x,T y) { return y.CompareTo(x); }private int Do(T x,T y) { return x.CompareTo(y); }public T Dequeue {get {var e = he[0];Pop();return e;}}public T Top { get { return he[0]; } }private void Extend() {T[] nhe = new T[max<<1];Array.Copy(he,nhe,max);he=nhe;max<<=1;}}public class Pt {private StringBuilder sb = new StringBuilder();public Pt(Action<Pt> f) { f(this); }public void W(int s) { sb.Append(s); }public void W(long s) { sb.Append(s); }public void W(double s) { sb.Append(s); }public void W(decimal s) { sb.Append(s); }public void W(char s) { sb.Append(s); }public void W(string s) { sb.Append(s); }public void W(object s) { sb.Append(s); }public void W(params object[] s) { sb.Append(string.Join(" ",s)); }public void Wl(int s) { sb.Append(s).AppendLine(); }public void Wl(long s) { sb.Append(s).AppendLine(); }public void Wl(double s) { sb.Append(s).AppendLine(); }public void Wl(decimal s) { sb.Append(s).AppendLine(); }public void Wl(char s) { sb.Append(s).AppendLine(); }public void Wl(string s) { sb.AppendLine(s); }public void Wl(object s) { sb.Append(s).AppendLine(); }public void Wl(int[] s) { sb.AppendLine(string.Join(" ",s)); }public void Wl(long[] s) { sb.AppendLine(string.Join(" ",s)); }public void Wl(double[] s) { sb.AppendLine(string.Join(" ",s)); }public void Wl(string[] s) { sb.AppendLine(string.Join(" ",s)); }public void Wl(params object[] s) { sb.AppendLine(string.Join(" ",s)); }public void Wl() { sb.AppendLine(); }public void Sm() { Console.Write(sb); }public void Op(StreamWriter sw) {sw.Write(sb);sw.Close();}public static bool operator ==(Pt a,Pt b) { return a.sb.ToString()==b.sb.ToString(); }public static bool operator !=(Pt a,Pt b) { return a.sb.ToString()!=b.sb.ToString(); }public override bool Equals(object obj) { return false; }public override int GetHashCode() { return 0; }}public class Sc {[MethodImpl(MethodImplOptions.AggressiveInlining)]protected virtual string Rl() { return Console.ReadLine(); }[MethodImpl(MethodImplOptions.AggressiveInlining)]protected virtual string[] Sp(string st) { return st.Split(); }[MethodImpl(MethodImplOptions.AggressiveInlining)]private T Ct<T>(string s) { return (T)Convert.ChangeType(s,typeof(T)); }public virtual int I { get { return int.Parse(Rl()); } }public virtual long L { get { return long.Parse(Rl()); } }public virtual double D { get { return double.Parse(Rl()); } }public virtual string S { get { return Rl(); } }public int[] Ia { get { return Array.ConvertAll(Sp(Rl()),int.Parse); } }public long[] La { get { return Array.ConvertAll(Sp(Rl()),long.Parse); } }public double[] Da { get { return Array.ConvertAll(Sp(Rl()),double.Parse); } }public string[] Sa { get { return Sp(Rl()); } }public object[] Oa { get { return Sp(Rl()); } }public int[] Ia2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),int.Parse); } }public int[] Ia3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),int.Parse); }public int[] Ia3(int a) { return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),int.Parse); }public long[] La2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),long.Parse); } }public long[] La3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),long.Parse); }public long[] La3(int a) { return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),long.Parse); }public double[] Da2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),double.Parse); } }public double[] Da3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),double.Parse); }public T[] Arr<T>(int n,Func<T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(); } return a; }public T[] Arr<T>(int n,Func<int,T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(i); } return a; }public T[] Arr<T>(int n,Func<string[],T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(Sp(Rl())); } return a; }public T[] Arr<T>(int n,Func<int,string[],T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(i,Sp(Rl())); } return a; }[MethodImpl(MethodImplOptions.AggressiveInlining)]public (T, T) Tp2<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1])); }[MethodImpl(MethodImplOptions.AggressiveInlining)]public (T, T, T) Tp3<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2])); }[MethodImpl(MethodImplOptions.AggressiveInlining)]public (T, T, T, T) Tp4<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3])); }[MethodImpl(MethodImplOptions.AggressiveInlining)]public (T, T, T, T, T) Tp5<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3]), Ct<T>(s[4])); }[MethodImpl(MethodImplOptions.AggressiveInlining)]public (T, T, T, T, T, T) Tp6<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3]), Ct<T>(s[4]), Ct<T>(s[5])); }[MethodImpl(MethodImplOptions.AggressiveInlining)]public (T1, T2) Tp2<T1, T2>() { var s = Sp(Rl()); return (Ct<T1>(s[0]), Ct<T2>(s[1])); }[MethodImpl(MethodImplOptions.AggressiveInlining)]public (T1, T1, T2) Tp3<T1, T2>() { var s = Sp(Rl()); return (Ct<T1>(s[0]), Ct<T1>(s[1]), Ct<T2>(s[2])); }}public class Scr:Sc {private List<string> li = new List<string>();private int l = 0;private bool bo = false;[MethodImpl(MethodImplOptions.AggressiveInlining)]protected override string Rl() {if(bo) { return li[l++%li.Count]; }li.Add(Console.ReadLine());return li[li.Count-1];}public void Again() { bo=true; }}public class Scs:Sc {private StreamReader sr;private string path;public Scs(string path) { sr=new StreamReader(this.path=path); }[MethodImpl(MethodImplOptions.AggressiveInlining)]protected override string Rl() { return sr.ReadLine(); }public void Close() { sr.Close(); }public void Reset() { sr=new StreamReader(path); }}public class Sc2:Sc {private string[] sps = new string[] { " "," ","\t" };[MethodImpl(MethodImplOptions.AggressiveInlining)]protected override string[] Sp(string st) { return st.Split(sps,StringSplitOptions.RemoveEmptyEntries); }public override int I { get { return int.Parse(Sp(Rl())[0]); } }public override long L { get { return long.Parse(Sp(Rl())[0]); } }public override double D { get { return double.Parse(Sp(Rl())[0]); } }public override string S { get { return Sp(Rl())[0]; } }}public class Scs2:Sc2 {private StreamReader sr;public Scs2(string t) { sr=new StreamReader(t); }[MethodImpl(MethodImplOptions.AggressiveInlining)]protected override string Rl() { return sr.ReadLine(); }public void Close() { sr.Close(); }}public class Sct:Sc {private List<string> li = new List<string>();private int l = 0;public void Add(int s) { li.Add(s.ToString()); }public void Add(long s) { li.Add(s.ToString()); }public void Add(double s) { li.Add(s.ToString()); }public void Add(string s) { li.Add(s.ToString()); }public void Add(object s) { li.Add(s.ToString()); }public void Add(int[] s) { li.Add(string.Join(" ",s)); }public void Add(long[] s) { li.Add(string.Join(" ",s)); }public void Add(double[] s) { li.Add(string.Join(" ",s)); }public void Add(string[] s) { li.Add(string.Join(" ",s)); }public void Add(params object[] s) { li.Add(string.Join(" ",s)); }protected override string Rl() { return li[l++]; }public void Clear() { li.Clear(); l=0; }public void Again() { l=0; }public void Pf() { Console.WriteLine(string.Join("\n",li)); }}