CODE FESTIVAL 2016 Final (Parallel)

Submission #1339167

Source codeソースコード

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

Task問題 J - Neue Spiel
User nameユーザ名 lei
Created time投稿日時
Language言語 C# (Mono 4.6.2.0)
Status状態 TLE
Score得点 2000
Source lengthソースコード長 9723 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
dataset1 2000 / 2000 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 0 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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
02-02.txt TLE
02-03.txt TLE
02-04.txt TLE
02-05.txt AC 21 ms 11092 KB
02-06.txt AC 20 ms 9044 KB
02-07.txt TLE
02-08.txt TLE
02-09.txt TLE
02-10.txt TLE
02-11.txt TLE
02-12.txt TLE
sample-01.txt AC 25 ms 13524 KB
sample-02.txt AC 21 ms 9172 KB