AtCoder Grand Contest 012

Submission #1357901

Source codeソースコード

using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Collections.Generic;
using System.Diagnostics;
using Enu = System.Linq.Enumerable;

public class Program
{
    static readonly int Mod = (int)1e9 + 7;

    public void Solve()
    {
        int N = Reader.Int(), X = Reader.Int(), Y = Reader.Int();
        var dic = new Dictionary<int, List<int>>();
        int[] C = new int[N], W = new int[N];
        for (int i = 0; i < N; i++)
        {
            C[i] = Reader.Int(); W[i] = Reader.Int();
            AddDic(dic, C[i], i);
        }
        if (dic.Count == 1) { Console.WriteLine(1); return; }

        var mins = new List<int>();
        var uf = new UnionFind(N);
        foreach (var A in dic.Values)
        {
            int minW = int.MaxValue, who = 0;
            foreach (int i in A)
                if (CheckMin(ref minW, W[i])) who = i;
            mins.Add(who);
            foreach (int i in A)
                if (minW + W[i] <= X) uf.Unite(who, i);
        }
        mins = mins.OrderBy(i => W[i]).ToList();
        foreach (var A in dic.Values)
            for (int mi = 0; mi < 2; mi++)
                if (C[mins[mi]] != C[A[0]])
                    foreach (int i in A)
                        if (W[mins[mi]] + W[i] <= Y) uf.Unite(mins[mi], i);
        long ans = 1;
        modC = new ModC(N, Mod);
        foreach (var A in uf.Components().Values)
        {
            var count = new Dictionary<int, List<int>>();
            foreach (int i in A) AddDic(count, C[i], 1);
            ans *= Count(count.Values.Select(v => v.Count).ToArray());
            ans %= Mod;
        }

        Console.WriteLine(ans);
    }


    ModC modC;
    long Count(int[] count)
    {
        int sum = count.Sum();
        long res = 1;
        foreach (int num in count)
        {
            res = res * modC[sum, num] % Mod;
            sum -= num;
        }
        return res;
    }

    bool CheckMin(ref int a, int b) { if (b < a) { a = b; return true; } return false; }

    void AddDic(Dictionary<int, List<int>> dic, int key, int val)
    {
        if (!dic.ContainsKey(key)) dic[key] = new List<int>();
        dic[key].Add(val);
    }
}

class ModC
{
    readonly long P;
    readonly long[] Fact, InvFact;

    public int this[int n, int k]
    {
        get
        {
            if (n < 0 || k < 0 || k > n) return 0;
            return (int)(Fact[n] * InvFact[k] % P * InvFact[n - k] % P);
        }
    }
    public ModC(int maxN, int p) // maxN < p, p is prime
    {
        P = p;
        Fact = new long[maxN + 1];
        InvFact = new long[maxN + 1];
        Fact[0] = 1;
        for (long i = 1; i <= maxN; i++)
            Fact[i] = Fact[i - 1] * i % P;
        InvFact[maxN] = ModPower(Fact[maxN], p - 2, p);
        for (int i = maxN - 1; i >= 0; i--)
            InvFact[i] = InvFact[i + 1] * (i + 1) % p;
    }
    long ModPower(long x, long n, long mod) // x ^ n
    {
        long res = 1;
        if ((x %= mod) < 0) x += mod;
        for (; n > 0; n >>= 1, x = x * x % mod)
            if ((n & 1) == 1) res = res * x % mod;
        return res;
    }
}

class UnionFind
{
    private int[] parent;
    private byte[] rank;

    public UnionFind(int N)
    {
        parent = new int[N];
        rank = new byte[N];
        for (int i = 0; i < N; i++) parent[i] = -1;
    }
    public int Root(int x)
    {
        if (parent[x] < 0) return x;
        return parent[x] = Root(parent[x]);
    }
    public bool Same(int x, int y)
    {
        return Root(x) == Root(y);
    }
    public int Count(int x)
    {
        return -parent[Root(x)];
    }
    public bool Unite(int x, int y)
    {
        x = Root(x); y = Root(y);
        if (x == y) return false;
        if (rank[x] > rank[y]) { var t = x; x = y; y = t; }
        if (rank[x] == rank[y]) rank[y]++;
        parent[y] += parent[x];
        parent[x] = y;
        return true;
    }
    public Dictionary<int, List<int>> Components()
    {
        var dic = new Dictionary<int, List<int>>();
        for (int i = 0; i < parent.Length; i++)
        {
            int root = Root(i);
            if (!dic.ContainsKey(root)) dic[root] = new List<int>();
            dic[root].Add(i);
        }
        return dic;
    }
}



class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
    static TextReader reader = Console.In;
    static readonly char[] separator = { ' ' };
    static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
    static string[] A = new string[0];
    static int i;
    static void Init() { Dispose(); A = new string[0]; }
    public static void Set(TextReader r) { Init(); reader = r; }
    public static void Set(string file) { Init(); reader = new StreamReader(file); }
    public static bool HasNext() { return CheckNext(); }
    public static string String() { return Next(); }
    public static int Int() { return int.Parse(Next()); }
    public static long Long() { return long.Parse(Next()); }
    public static double Double() { return double.Parse(Next()); }
    public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
    public static int[] IntArray(int N) { return Range(N, Int); }
    public static int[][] IntTable(int H) { return Range(H, IntLine); }
    public static string[] StringArray(int N) { return Range(N, Next); }
    public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
    public static string Line() { return reader.ReadLine().Trim(); }
    public static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; }
    public static void Dispose() { reader.Dispose(); }
    static string[] Split(string s) { return s.Split(separator, op); }
    static string Next() { CheckNext(); return A[i++]; }
    static bool CheckNext()
    {
        if (i < A.Length) return true;
        string line = reader.ReadLine();
        if (line == null) return false;
        if (line == "") return CheckNext();
        A = Split(line);
        i = 0;
        return true;
    }
}

Submission

Task問題 D - Colorful Balls
User nameユーザ名 eitaho
Created time投稿日時
Language言語 C# (Mono 4.6.2.0)
Status状態 AC
Score得点 1000
Source lengthソースコード長 6296 Byte
File nameファイル名
Exec time実行時間 560 ms
Memory usageメモリ使用量 73504 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt,00_example_03.txt
All 1000 / 1000 00_example_01.txt,00_example_02.txt,00_example_03.txt,01.txt,02.txt,03.txt,04.txt,05.txt,06.txt,07.txt,08.txt,09.txt,10.txt,11.txt,12.txt,13.txt,14.txt,15.txt,16.txt,17.txt,18.txt,19.txt,20.txt,21.txt,22.txt,23.txt,24.txt,25.txt,26.txt,27.txt,28.txt,29.txt,30.txt,31.txt,32.txt,33.txt,34.txt,35.txt,36.txt,37.txt,38.txt,39.txt,40.txt,41.txt,42.txt,43.txt,44.txt,45.txt,46.txt,47.txt,48.txt,49.txt,50.txt,51.txt,52.txt,53.txt,54.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_example_01.txt AC 37 ms 11996 KB
00_example_02.txt AC 24 ms 11232 KB
00_example_03.txt AC 31 ms 9440 KB
01.txt AC 32 ms 9524 KB
02.txt AC 32 ms 13536 KB
03.txt AC 44 ms 14432 KB
04.txt AC 31 ms 9440 KB
05.txt AC 37 ms 11872 KB
06.txt AC 33 ms 11488 KB
07.txt AC 215 ms 33168 KB
08.txt AC 32 ms 11572 KB
09.txt AC 108 ms 17104 KB
10.txt AC 86 ms 18904 KB
11.txt AC 32 ms 13536 KB
12.txt AC 32 ms 13652 KB
13.txt AC 46 ms 14944 KB
14.txt AC 31 ms 11488 KB
15.txt AC 112 ms 22936 KB
16.txt AC 246 ms 37172 KB
17.txt AC 57 ms 16988 KB
18.txt AC 103 ms 24976 KB
19.txt AC 186 ms 29292 KB
20.txt AC 525 ms 66736 KB
21.txt AC 538 ms 70188 KB
22.txt AC 554 ms 64656 KB
23.txt AC 501 ms 66292 KB
24.txt AC 560 ms 66932 KB
25.txt AC 532 ms 63792 KB
26.txt AC 510 ms 59448 KB
27.txt AC 531 ms 58596 KB
28.txt AC 506 ms 64056 KB
29.txt AC 521 ms 63248 KB
30.txt AC 558 ms 73452 KB
31.txt AC 512 ms 62904 KB
32.txt AC 559 ms 63204 KB
33.txt AC 509 ms 59888 KB
34.txt AC 458 ms 55160 KB
35.txt AC 328 ms 32004 KB
36.txt AC 358 ms 33352 KB
37.txt AC 326 ms 34292 KB
38.txt AC 325 ms 31788 KB
39.txt AC 330 ms 32720 KB
40.txt AC 473 ms 59964 KB
41.txt AC 531 ms 60940 KB
42.txt AC 543 ms 69224 KB
43.txt AC 560 ms 66356 KB
44.txt AC 507 ms 65272 KB
45.txt AC 554 ms 73504 KB
46.txt AC 530 ms 63236 KB
47.txt AC 219 ms 16692 KB
48.txt AC 226 ms 16692 KB
49.txt AC 223 ms 18740 KB
50.txt AC 407 ms 54328 KB
51.txt AC 413 ms 56576 KB
52.txt AC 310 ms 39248 KB
53.txt AC 314 ms 39812 KB
54.txt AC 313 ms 42320 KB