Submission #311881


Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;

class Myon
{
    public Myon() { }
    public static int Main()
    {

        rnd = new XRand();
        new Myon().calc();
        return 0;
    }
    static XRand rnd;


    class Work:IComparable<Work>
    {
        public int start, goal, id;

        public Work(int start, int goal, int id)
        {
            this.start = start;
            this.goal = goal;
            this.id = id;
        }

        public int CompareTo(Work w)
        {
            if (start.CompareTo(w.start) != 0) return start.CompareTo(w.start);
            if (goal.CompareTo(w.goal) != 0) return goal.CompareTo(w.goal);
            return id.CompareTo(w.id);
        }
    }

    void calc()
    {
        Scanner cin = new Scanner();
        int N = cin.nextInt();
        int[] a = new int[N];
        int[] b = new int[N];
        for (int i = 0; i < N; i++)
        {
            a[i] = cin.nextInt();
            b[i] = cin.nextInt();
        }

        int MAX = 1000010;
        int[] dp_num = new int[MAX]; //時刻iの時にdp_num[i]個取れる
        int[] dp_next = new int[MAX]; //dp_num[i]個取れる中で、最もidが小さい

        Work[] works = new Work[N];
        for (int i = 0; i < N; i++)
        {
            works[i] = new Work(a[i], b[i], i);
        }
        Array.Sort(works);


        int now = N - 1;
        for (int i = MAX - 2; i >= 0; i--)
        {
            dp_num[i] = dp_num[i + 1];
            dp_next[i] = dp_next[i + 1];

            while (now >= 0)
            {
                if (works[now].start == i)
                {
                    int next_num = dp_num[works[now].goal] + 1;
                    int next_next = works[now].id;

                    if(next_num > dp_num[i] ||
                        ((next_num == dp_num[i]) && next_next < dp_next[i]))
                    {
                        dp_num[i] = next_num;
                        dp_next[i] = next_next;
                    }
                    now--;
                }
                else
                {
                    break;
                }
            }
        }

        List<int> ret = new List<int>();
        now = 0;
        while (dp_num[now] > 0)
        {
            ret.Add(dp_next[now] + 1);
            now = b[dp_next[now]];
        }

        Console.WriteLine(ret.Count);
        Console.WriteLine(String.Join(" ", ret));


    }


}




class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        do
        {
            s = Console.ReadLine().Split(cs, StringSplitOptions.RemoveEmptyEntries);
        } while ((s.Length == 1 && s[0] == "") || s.Length == 0);
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

class XRand
{
    uint x, y, z, w;


    public XRand()
    {
        init();
    }

    public XRand(uint s)
    {
        init();
        init_xor128(s);
    }

    void init()
    {
        x = 314159265; y = 358979323; z = 846264338; w = 327950288;

    }

    public void init_xor128(uint s)
    {
        z ^= s;
        z ^= z >> 21; z ^= z << 35; z ^= z >> 4;
        z *= 736338717;
    }

    uint next()
    {
        uint t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8;
    }

    public long nextLong(long m)
    {
        return (long)((((ulong)next() << 32) + next()) % (ulong)m);
    }

    public int nextInt(int m)
    {
        return (int)(next() % m);
    }

    public long nextLong(long min, long max)
    {
        return min + nextLong(max - min + 1);
    }

    public int nextInt(int min, int max)
    {
        return min + nextInt(max - min + 1);
    }

    public int nextIntP(int a)
    {
        return (int)Math.Pow(a, nextDouble());
    }

    public int nextIntP(int min, int max)
    {
        int diff = max - min;
        return min + nextIntP(diff + 2) - 1;
    }

    public long nextLongP(long a)
    {
        return (long)Math.Pow(a, nextDouble());
    }

    public long nextLongP(long min, long max)
    {
        long diff = max - min;
        return min + nextLongP(diff + 2) - 1;
    }


    public double nextDouble()
    {
        return (double)next() / uint.MaxValue;
    }

    public double nextDoubleP(double a)
    {
        return Math.Pow(a, nextDouble());
    }
}

Submission Info

Submission Time
Task C - 仕事計画
User chokudai
Language C# (Mono 2.10.8.1)
Score 100
Code Size 4966 Byte
Status AC
Exec Time 418 ms
Memory 26916 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 24
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All 0.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt
Case Name Status Exec Time Memory
0.txt AC 146 ms 15772 KB
1.txt AC 144 ms 15780 KB
10.txt AC 146 ms 15760 KB
11.txt AC 148 ms 15760 KB
12.txt AC 152 ms 15896 KB
13.txt AC 151 ms 15860 KB
14.txt AC 151 ms 15896 KB
15.txt AC 151 ms 15900 KB
16.txt AC 150 ms 15896 KB
17.txt AC 153 ms 15908 KB
18.txt AC 363 ms 20576 KB
19.txt AC 362 ms 20592 KB
2.txt AC 145 ms 15652 KB
20.txt AC 379 ms 20636 KB
21.txt AC 367 ms 20576 KB
22.txt AC 368 ms 20764 KB
23.txt AC 418 ms 26916 KB
3.txt AC 147 ms 15712 KB
4.txt AC 143 ms 15728 KB
5.txt AC 139 ms 15800 KB
6.txt AC 150 ms 15768 KB
7.txt AC 151 ms 15900 KB
8.txt AC 156 ms 15760 KB
9.txt AC 174 ms 15872 KB
sample1.txt AC 157 ms 15736 KB
sample2.txt AC 171 ms 15772 KB
sample3.txt AC 171 ms 15776 KB