AtCoder Grand Contest 012

Submission #1357890

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)
            foreach (int i in A)
                for (int mi = 0; mi < 2; mi++)
                    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状態 WA
Score得点 0
Source lengthソースコード長 6243 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt,00_example_03.txt
All 0 / 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 31 ms 13536 KB
00_example_02.txt AC 25 ms 11232 KB
00_example_03.txt AC 32 ms 13536 KB
01.txt AC 32 ms 11488 KB
02.txt AC 32 ms 11488 KB
03.txt AC 43 ms 12256 KB
04.txt AC 31 ms 11488 KB
05.txt AC 37 ms 11872 KB
06.txt AC 33 ms 13596 KB
07.txt AC 217 ms 33168 KB
08.txt AC 32 ms 11488 KB
09.txt AC 108 ms 23248 KB
10.txt AC 85 ms 16856 KB
11.txt AC 32 ms 9524 KB
12.txt AC 32 ms 11488 KB
13.txt AC 45 ms 12896 KB
14.txt AC 31 ms 9440 KB
15.txt AC 117 ms 24984 KB
16.txt AC 250 ms 37172 KB
17.txt AC 58 ms 21084 KB
18.txt AC 102 ms 20880 KB
19.txt AC 187 ms 29292 KB
20.txt AC 528 ms 66864 KB
21.txt AC 544 ms 66220 KB
22.txt AC 536 ms 68112 KB
23.txt AC 512 ms 64244 KB
24.txt AC 545 ms 71028 KB
25.txt AC 525 ms 65968 KB
26.txt AC 499 ms 60728 KB
27.txt AC 523 ms 57300 KB
28.txt AC 507 ms 61368 KB
29.txt AC 541 ms 67344 KB
30.txt AC 575 ms 73324 KB
31.txt AC 505 ms 63924 KB
32.txt AC 549 ms 62948 KB
33.txt AC 514 ms 62188 KB
34.txt AC 461 ms 60164 KB
35.txt WA
36.txt AC 362 ms 35400 KB
37.txt WA
38.txt WA
39.txt AC 327 ms 32720 KB
40.txt AC 486 ms 59324 KB
41.txt AC 524 ms 64772 KB
42.txt AC 543 ms 73548 KB
43.txt AC 549 ms 64476 KB
44.txt AC 502 ms 63732 KB
45.txt AC 560 ms 69408 KB
46.txt AC 536 ms 63896 KB
47.txt AC 219 ms 18744 KB
48.txt AC 223 ms 18744 KB
49.txt AC 226 ms 18744 KB
50.txt AC 408 ms 52232 KB
51.txt AC 411 ms 56576 KB
52.txt AC 318 ms 41928 KB
53.txt AC 321 ms 41808 KB
54.txt AC 312 ms 39248 KB