Submission #1339167
Source Code Expand
using System; using System.Text; using System.Collections.Generic; class Solve{ int N; int[] count; int[] state; public Solve(){} StringBuilder sb; public static int Main(){ new Solve().Run(); return 0; } void Run(){ sb = new StringBuilder(); Calc(); Console.Write(sb.ToString()); } void Calc(){ N = int.Parse(Console.ReadLine()); int[] U = new int[N]; int[] D = new int[N]; int[] L = new int[N]; int[] R = new int[N]; string[] str = Console.ReadLine().Split(' '); for(int i=0;i<N;i++){ U[i] = int.Parse(str[i]); } str = Console.ReadLine().Split(' '); for(int i=0;i<N;i++){ D[i] = int.Parse(str[i]); } str = Console.ReadLine().Split(' '); for(int i=0;i<N;i++){ L[i] = int.Parse(str[i]); } str = Console.ReadLine().Split(' '); for(int i=0;i<N;i++){ R[i] = int.Parse(str[i]); } { bool b = true; for(int i=0;i<N;i++){ b &= U[i] + D[i] <= N; b &= L[i] + R[i] <= N; } if(!b){ sb.Append("NO\n"); return; } } int l = N*N; int r = N*N + N; int u = N*N + 2*N; int d = N*N + 3*N; int s = N*N + 4*N; int g = N*N + 4*N + 1; List<int> f = new List<int>(); List<int> t = new List<int>(); List<long> capa = new List<long>(); List<long> cost = new List<long>(); for(int i=0;i<N;i++){ f.Add(s); t.Add(l+i); capa.Add(L[i]); cost.Add(0); f.Add(s); t.Add(r+i); capa.Add(R[i]); cost.Add(0); f.Add(s); t.Add(u+i); capa.Add(U[i]); cost.Add(0); f.Add(s); t.Add(d+i); capa.Add(D[i]); cost.Add(0); } for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ f.Add(l+i); t.Add(i*N+j); capa.Add(1); cost.Add(j); f.Add(r+i); t.Add(i*N+j); capa.Add(1); cost.Add(N-1-j); f.Add(u+j); t.Add(i*N+j); capa.Add(1); cost.Add(i); f.Add(d+j); t.Add(i*N+j); capa.Add(1); cost.Add(N-1-i); f.Add(i*N+j); t.Add(g); capa.Add(1); cost.Add(0); } } MinCostFlow F = new MinCostFlow(f.ToArray(),t.ToArray(),capa.ToArray(),cost.ToArray(),g+1,s,g,N*N); state = new int[N*N]; for(int i=0;i<N;i++){ Vertex V = F.point[l+i]; for(int j=1;j<=N;j++){ if(V.edges[j].capacity == 0){ state[i*N+j-1] = 2; } } V = F.point[r+i]; for(int j=1;j<=N;j++){ if(V.edges[j].capacity == 0){ state[i*N+j-1] = 3; } } V = F.point[d+i]; for(int j=1;j<=N;j++){ if(V.edges[j].capacity == 0){ state[(j-1)*N+i] = 1; } } } count = new int[N*N]; for(int i=0;i<N*N;i++){ if(state[i] == 0){ count[i] = i/N; } if(state[i] == 1){ count[i] = N - 1 - i/N; } if(state[i] == 2){ count[i] = i%N; } if(state[i] == 3){ count[i] = N - 1 - i%N; } } for(int i=0;i<N*N;i++){ if(count[i] == 0){ Calc(i/N,i%N); } } } void Calc(int h,int w){ count[h*N+w]--; if(state[h*N+w] == 0){ sb.Append("U"+(w+1)+"\n"); } if(state[h*N+w] == 1){ sb.Append("D"+(w+1)+"\n"); } if(state[h*N+w] == 2){ sb.Append("L"+(h+1)+"\n"); } if(state[h*N+w] == 3){ sb.Append("R"+(h+1)+"\n"); } for(int i=0;i<h;i++){ if(state[i*N+w] == 1){ count[i*N+w]--; if(count[i*N+w] == 0){ Calc(i,w); } } } for(int i=h+1;i<N;i++){ if(state[i*N+w] == 0){ count[i*N+w]--; if(count[i*N+w] == 0){ Calc(i,w); } } } for(int i=0;i<w;i++){ if(state[h*N+i] == 3){ count[h*N+i]--; if(count[h*N+i] == 0){ Calc(h,i); } } } for(int i=w+1;i<N;i++){ if(state[h*N+i] == 2){ count[h*N+i]--; if(count[h*N+i] == 0){ Calc(h,i); } } } } } class Edge{ public Vertex to; public long capacity; public long cost; public Edge rev; public Edge(Vertex v,long ca,long co){ to = v; capacity = ca; cost = co; } } class Vertex{ public bool finished; public long cost; public long h; public Vertex fromv; public Edge frome; public List<Edge> edges; public void AddEdge(Edge e){ edges.Add(e); } public Vertex(){ edges = new List<Edge>(); finished = false; cost = -1; } } struct Data{ public Vertex v; public long cost; public Data(Vertex v0,long c){ v = v0; cost = c; } } class MinCostFlow{ public Vertex[] point; Vertex S; Vertex G; public long res; int E; const long INF = 1000000000000000; public MinCostFlow(int[] f,int[] t,long[] capacity,long[] cost,int n,int s,int g,long flow){ point = new Vertex[n]; for(int i=0;i<n;i++){ point[i] = new Vertex(); } E = f.Length; for(int i=0;i<E;i++){ point[f[i]].AddEdge(new Edge(point[t[i]],capacity[i],cost[i])); point[t[i]].AddEdge(new Edge(point[f[i]],0,-cost[i])); point[f[i]].edges[point[f[i]].edges.Count-1].rev = point[t[i]].edges[point[t[i]].edges.Count-1]; point[t[i]].edges[point[t[i]].edges.Count-1].rev = point[f[i]].edges[point[f[i]].edges.Count-1]; } S = point[s]; G = point[g]; res = 0; while(true){ Heap H = new Heap(2*E+1); S.cost = 0; H.push(new Data(S,0)); while(!H.Empty()){ Data D = H.pop(); Vertex V = D.v; if(V.finished){ continue; } V.finished = true; for(int i=0;i<V.edges.Count;i++){ if(V.edges[i].capacity == 0){ continue; } Vertex T = V.edges[i].to; if(T.cost == -1 || T.cost > V.cost + V.edges[i].cost + V.h - T.h){ T.cost = V.cost + V.edges[i].cost + V.h - T.h; T.fromv = V; T.frome = V.edges[i]; H.push(new Data(T,T.cost)); } } } if(G.cost == -1){ res = -1; break; } for(int i=0;i<n;i++){ point[i].h += point[i].cost; point[i].cost = -1; point[i].finished = false; } long d = flow; for(Vertex V = G;V != S;V = V.fromv){ d = Math.Min(d,V.frome.capacity); } res += d*G.h; for(Vertex V = G;V != S;V = V.fromv){ V.frome.capacity -= d; V.frome.rev.capacity += d; } flow -= d; if(flow == 0){ break; } } } } class Heap{ public int size; Data[] obj; public Heap(int maxsize){ size = 0; obj = new Data[maxsize]; } public void push(Data a){ int i = size; size++; while(i > 0){ int p = (i - 1)/2; if(obj[p].cost <= a.cost){ obj[i] = a; break; } obj[i] = obj[p]; i = p; } if(i == 0){ obj[0] = a; } } public bool Empty(){ return size == 0; } public Data pop(){ Data t = obj[0]; int i = 0; size--; while(2*i+1 < size){ int p = 2*i+1; if(p+1 < size && obj[p+1].cost < obj[p].cost){ p++; } if(obj[p].cost < obj[size].cost){ obj[i] = obj[p]; i = p; } else{ obj[i] = obj[size]; break; } } if(2*i+1 >= size){ obj[i] = obj[size]; } return t; } }
Submission Info
Submission Time | |
---|---|
Task | J - Neue Spiel |
User | leign |
Language | C# (Mono 4.6.2.0) |
Score | 2000 |
Code Size | 9723 Byte |
Status | TLE |
Exec Time | 4214 ms |
Memory | 126836 KB |
Judge Result
Set Name | sample | dataset1 | dataset2 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 2000 / 2000 | 0 / 100 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt |
dataset1 | sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt |
dataset2 | sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, sample-01.txt, sample-02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 25 ms | 11476 KB |
01-02.txt | AC | 25 ms | 11476 KB |
01-03.txt | AC | 25 ms | 13524 KB |
01-04.txt | AC | 27 ms | 10464 KB |
01-05.txt | AC | 76 ms | 28896 KB |
01-06.txt | AC | 368 ms | 29144 KB |
01-07.txt | AC | 1338 ms | 32312 KB |
01-08.txt | AC | 1336 ms | 30248 KB |
01-09.txt | AC | 62 ms | 25312 KB |
01-10.txt | AC | 1138 ms | 30368 KB |
01-11.txt | AC | 1273 ms | 30248 KB |
01-12.txt | AC | 1305 ms | 28216 KB |
01-13.txt | AC | 1265 ms | 32312 KB |
01-14.txt | AC | 21 ms | 11220 KB |
01-15.txt | AC | 968 ms | 29920 KB |
01-16.txt | AC | 1337 ms | 28216 KB |
01-17.txt | AC | 1330 ms | 32296 KB |
01-18.txt | AC | 1326 ms | 32296 KB |
01-19.txt | AC | 20 ms | 9044 KB |
01-20.txt | AC | 1280 ms | 28312 KB |
01-21.txt | AC | 1289 ms | 32296 KB |
01-22.txt | AC | 21 ms | 11092 KB |
01-23.txt | AC | 21 ms | 9044 KB |
01-24.txt | AC | 1294 ms | 28200 KB |
01-25.txt | AC | 1297 ms | 30360 KB |
01-26.txt | AC | 21 ms | 13268 KB |
01-27.txt | AC | 250 ms | 31312 KB |
01-28.txt | AC | 1175 ms | 30368 KB |
01-29.txt | AC | 1313 ms | 32296 KB |
01-30.txt | AC | 1297 ms | 30248 KB |
01-31.txt | AC | 21 ms | 9172 KB |
01-32.txt | AC | 1309 ms | 30248 KB |
01-33.txt | AC | 21 ms | 11092 KB |
01-34.txt | AC | 1296 ms | 28200 KB |
01-35.txt | AC | 453 ms | 30384 KB |
01-36.txt | AC | 505 ms | 30344 KB |
01-37.txt | AC | 21 ms | 11220 KB |
01-38.txt | AC | 1181 ms | 30392 KB |
01-39.txt | AC | 1348 ms | 28312 KB |
01-40.txt | AC | 927 ms | 30456 KB |
01-41.txt | AC | 1015 ms | 30360 KB |
01-42.txt | AC | 1012 ms | 32312 KB |
01-43.txt | AC | 927 ms | 30264 KB |
01-44.txt | AC | 1020 ms | 30248 KB |
01-45.txt | AC | 927 ms | 30248 KB |
01-46.txt | AC | 1019 ms | 28312 KB |
02-01.txt | TLE | 4210 ms | 122488 KB |
02-02.txt | TLE | 4213 ms | 126836 KB |
02-03.txt | TLE | 4214 ms | 122636 KB |
02-04.txt | TLE | 4214 ms | 120216 KB |
02-05.txt | AC | 21 ms | 11092 KB |
02-06.txt | AC | 20 ms | 9044 KB |
02-07.txt | TLE | 4214 ms | 118436 KB |
02-08.txt | TLE | 4214 ms | 121348 KB |
02-09.txt | TLE | 4214 ms | 116116 KB |
02-10.txt | TLE | 4214 ms | 123012 KB |
02-11.txt | TLE | 4213 ms | 117460 KB |
02-12.txt | TLE | 4214 ms | 118148 KB |
sample-01.txt | AC | 25 ms | 13524 KB |
sample-02.txt | AC | 21 ms | 9172 KB |