Submission #214298


Source Code Expand

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

class Program
{
    void Solve()
    {
        int N = reader.Int(), M = reader.Int(), Pow = reader.Int();
        int[] after = new int[N];
        var Eindex = Enu.Range(0, N).Select(i => new List<int>()).ToArray();
        var Eto = Enu.Range(0, N).Select(i => new List<int>()).ToArray();

        for (int i = 0; i < M; i++)
        {
            int R = reader.Int();
            Eindex[R - 1].Add(i);
            Eto[R - 1].Add(R);
            Eindex[R].Add(i);
            Eto[R].Add(R - 1);
        }
        for (int i = 0; i < N; i++)
        {
            int curr = i;
            int ei = 0;
            while (true)
            {
                int index = LowerBound(Eindex[curr], ei);
                if (index >= Eindex[curr].Count) break;
                ei = Eindex[curr][index] + 1;
                curr = Eto[curr][index];
            }
            after[i] = curr;
        }

        int[] res = (int[])after.Clone();
        Pow--;
        while (Pow > 0)
        {
            if (Pow % 2 == 1) res = Next(res, after);
            after = Next(after, after);
            Pow /= 2;
        }
        res = res.Select(x => x + 1).ToArray();

        Console.WriteLine(string.Join("\n", res));
        Console.ReadLine();
    }

    int[] Next(int[] a, int[] b)
    {
        int[] res = new int[a.Length];
        for (int i = 0; i < res.Length; i++)
            res[i] = b[a[i]];
        return res;
    }

    static int LowerBound<T>(List<T> a, T val)
    {
        var comp = Comparer<T>.Default;
        int left = -1, right = a.Count;
        while (right - left > 1)
        {
            int mid = (left + right) / 2;
            if (comp.Compare(a[mid], val) >= 0) { right = mid; }
            else { left = mid; }
        }
        return right;
    }



    static void Main() { new Program().Solve(); }
    Reader reader = new Reader(Console.In);
    class Reader
    {
        private readonly TextReader reader;
        private readonly char[] separator = new char[] { ' ' };
        private readonly StringSplitOptions removeOp = StringSplitOptions.RemoveEmptyEntries;
        private string[] A = new string[0];
        private int i;

        public Reader(TextReader r) { reader = r; }
        public bool HasNext() { return Enqueue(); }
        public string String() { return Dequeue(); }
        public int Int() { return int.Parse(Dequeue()); }
        public long Long() { return long.Parse(Dequeue()); }
        public double Double() { return double.Parse(Dequeue()); }
        public int[] IntLine() { var s = Line(); return s == "" ? new int[0] : Array.ConvertAll(Split(s), int.Parse); }
        public int[] IntArray(int N) { return Enumerable.Range(0, N).Select(i => Int()).ToArray(); }
        public int[][] IntGrid(int H) { return Enumerable.Range(0, H).Select(i => IntLine()).ToArray(); }
        public string[] StringArray(int N) { return Enumerable.Range(0, N).Select(i => Line()).ToArray(); }
        public string Line() { return reader.ReadLine().Trim(); }
        private string[] Split(string s) { return s.Split(separator, removeOp); }
        private bool Enqueue()
        {
            if (i < A.Length) return true;
            string line = reader.ReadLine();
            if (line == null) return false;
            if (line == "") return Enqueue();
            A = Split(line);
            i = 0;
            return true;
        }
        private string Dequeue() { Enqueue(); return A[i++]; }
    }
}

Submission Info

Submission Time
Task D - 阿弥陀
User eitaho
Language C# (Mono 2.10.8.1)
Score 100
Code Size 3788 Byte
Status AC
Exec Time 642 ms
Memory 54540 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 10 / 10 20 / 20 20 / 20 50 / 50
Status
AC × 9
AC × 18
AC × 18
AC × 29
Set Name Test Cases
Subtask1 sample_1.txt, 01_i.txt, 01_random01.txt, 01_random02.txt, 01_random03.txt, 01_random04.txt, 01_random05.txt, 01_random06.txt, 01_random07.txt
Subtask2 sample_1.txt, sample_2.txt, sample_3.txt, 02_i.txt, 02_p.txt, 02_random01.txt, 02_random02.txt, 02_random03.txt, 02_random04.txt, 02_random05.txt, 02_random06.txt, 02_random07.txt, 02_random08.txt, 02_rp01.txt, 02_rp02.txt, 02_rp03.txt, 02_rp04.txt, 02_rp05.txt
Subtask3 sample_1.txt, sample_2.txt, 03_i.txt, 03_random01.txt, 03_random02.txt, 03_random03.txt, 03_random04.txt, 03_random05.txt, 03_random06.txt, 03_random07.txt, 03_random08.txt, 03_random09.txt, 03_random10.txt, 03_random11.txt, 03_random12.txt, 03_random13.txt, 03_random14.txt, 03_random15.txt
Subtask4 sample_1.txt, sample_2.txt, sample_3.txt, 04_i.txt, 04_p1.txt, 04_p2.txt, 04_random01.txt, 04_random02.txt, 04_random03.txt, 04_random04.txt, 04_random05.txt, 04_random06.txt, 04_random07.txt, 04_random08.txt, 04_random09.txt, 04_random10.txt, 04_random11.txt, 04_random12.txt, 04_random13.txt, 04_rp01.txt, 04_rp02.txt, 04_rp03.txt, 04_rp04.txt, 04_rp05.txt, 04_rp06.txt, 04_rp07.txt, 04_rp08.txt, 04_rp09.txt, 04_rp10.txt
Case Name Status Exec Time Memory
01_i.txt AC 580 ms 47240 KB
01_random01.txt AC 406 ms 8972 KB
01_random02.txt AC 163 ms 8968 KB
01_random03.txt AC 164 ms 8960 KB
01_random04.txt AC 181 ms 10756 KB
01_random05.txt AC 322 ms 29444 KB
01_random06.txt AC 527 ms 46204 KB
01_random07.txt AC 616 ms 49928 KB
02_i.txt AC 180 ms 9480 KB
02_p.txt AC 166 ms 9352 KB
02_random01.txt AC 163 ms 9100 KB
02_random02.txt AC 162 ms 8968 KB
02_random03.txt AC 171 ms 9604 KB
02_random04.txt AC 165 ms 9228 KB
02_random05.txt AC 182 ms 11140 KB
02_random06.txt AC 259 ms 18052 KB
02_random07.txt AC 372 ms 27272 KB
02_random08.txt AC 372 ms 27388 KB
02_rp01.txt AC 168 ms 9356 KB
02_rp02.txt AC 169 ms 9352 KB
02_rp03.txt AC 167 ms 9348 KB
02_rp04.txt AC 165 ms 9340 KB
02_rp05.txt AC 167 ms 9336 KB
03_i.txt AC 163 ms 8964 KB
03_random01.txt AC 185 ms 10760 KB
03_random02.txt AC 377 ms 23944 KB
03_random03.txt AC 344 ms 23688 KB
03_random04.txt AC 334 ms 22240 KB
03_random05.txt AC 195 ms 11656 KB
03_random06.txt AC 188 ms 10888 KB
03_random07.txt AC 207 ms 12664 KB
03_random08.txt AC 167 ms 9340 KB
03_random09.txt AC 222 ms 13704 KB
03_random10.txt AC 273 ms 18312 KB
03_random11.txt AC 346 ms 21256 KB
03_random12.txt AC 357 ms 21640 KB
03_random13.txt AC 313 ms 19976 KB
03_random14.txt AC 284 ms 19464 KB
03_random15.txt AC 210 ms 12532 KB
04_i.txt AC 610 ms 50312 KB
04_p1.txt AC 392 ms 46172 KB
04_p2.txt AC 339 ms 36096 KB
04_random01.txt AC 411 ms 32620 KB
04_random02.txt AC 303 ms 24280 KB
04_random03.txt AC 301 ms 23048 KB
04_random04.txt AC 388 ms 29320 KB
04_random05.txt AC 364 ms 28412 KB
04_random06.txt AC 380 ms 33160 KB
04_random07.txt AC 505 ms 39428 KB
04_random08.txt AC 442 ms 34552 KB
04_random09.txt AC 451 ms 34212 KB
04_random10.txt AC 338 ms 27656 KB
04_random11.txt AC 641 ms 54540 KB
04_random12.txt AC 642 ms 54020 KB
04_random13.txt AC 639 ms 54156 KB
04_rp01.txt AC 387 ms 41096 KB
04_rp02.txt AC 382 ms 40324 KB
04_rp03.txt AC 385 ms 40580 KB
04_rp04.txt AC 393 ms 40716 KB
04_rp05.txt AC 388 ms 41092 KB
04_rp06.txt AC 388 ms 41184 KB
04_rp07.txt AC 383 ms 41100 KB
04_rp08.txt AC 387 ms 40800 KB
04_rp09.txt AC 383 ms 41096 KB
04_rp10.txt AC 389 ms 40712 KB
sample_1.txt AC 164 ms 8964 KB
sample_2.txt AC 165 ms 8972 KB
sample_3.txt AC 164 ms 8976 KB