提出 #539248


ソースコード 拡げる

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Problem : IDisposable
{
	private Scanner sc;
	private Printer pr;
	public Problem()
	{
		sc = new Scanner();
		pr = new Printer();
		Initiate();
	}
	public void Dispose()
	{
		pr.Dispose();
		sc.Dispose();
	}
	private int N, a;
	private string k;
	private int[] b;
	private void Initiate()
	{
		sc.Read(out N, out a);
		sc.Read(out k);
		b = sc.ReadMany<int>(N);
	}
	public void Solve()
	{
		if (a == 1 && k == "1")
		{
			pr.WriteLine(b[0]);
			return;
		}
		for (int i = 0; i < N; i++)
		{
			b[i]--;
		}
		a--;
		var stock = new int[N];
		stock[a] = 1;
		int foot = a;
		int length = N;
		int reminder = 0;
		for (int i = 1; i < N; i++)
		{
			if (stock[b[foot]] > 0)
			{ length = i + 1 - stock[b[foot]]; reminder = stock[b[foot]] - 1; break; }
			else
			{
				foot = b[foot];
				stock[foot] = i + 1;
			}
		}
		int kModLength = 0;
		for (int i = 0; i < k.Length; i++)
		{
			kModLength = (kModLength * 10 + k[i] - '0') % length;
		}

		var hoge = kModLength - reminder%length;
		while(hoge<0)
		{
			hoge += length;
		}

		int result = b[foot];
		for (var i = 0; i < hoge; i++)
		{
			result = b[result];
		}
		result++;

		Console.WriteLine(result);


	}
}
class Program
{
	static void Main()
	{
		using (var problem = new Problem()) problem.Solve();
	}
}
class Pair<S, T>
{
	public S First;
	public T Second;
	public Pair() { First = default(S); Second = default(T); }
	public Pair(S s, T t) { First = s; Second = t; }
	public override string ToString() { return "(" + First + ", " + Second + ")"; }
	public override int GetHashCode() { return First.GetHashCode() ^ Second.GetHashCode(); }
	public override bool Equals(object obj)
	{
		if (ReferenceEquals(this, obj)) return true;
		else if (obj == null) return false;
		var tmp = obj as Pair<S, T>;
		return (object)tmp != null && First.Equals(tmp.First) && Second.Equals(tmp.Second);
	}
}
class Point : Pair<int, int>
{
	public int X { get { return First; } set { First = value; } }
	public int Y { get { return Second; } set { Second = value; } }
	public Point() : base(0, 0) { }
	public Point(int x, int y) : base(x, y) { }
	public IEnumerable<Point> Neighbors4()
	{
		yield return new Point(X - 1, Y);
		yield return new Point(X, Y - 1);
		yield return new Point(X, Y + 1);
		yield return new Point(X + 1, Y);
	}
	public IEnumerable<Point> Neighbors8()
	{
		yield return new Point(X - 1, Y - 1);
		yield return new Point(X - 1, Y);
		yield return new Point(X - 1, Y + 1);
		yield return new Point(X, Y - 1);
		yield return new Point(X, Y + 1);
		yield return new Point(X + 1, Y - 1);
		yield return new Point(X + 1, Y);
		yield return new Point(X + 1, Y + 1);
	}
}
class Printer : IDisposable
{
	private TextWriter file;
	public Printer() { file = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; }
	public Printer(string path) { file = new StreamWriter(path, false) { AutoFlush = false }; }
	public void Write<T>(T value) { file.Write(value); }
	public void Write(string str, params object[] args) { file.Write(str, args); }
	public void WriteLine() { file.WriteLine(); }
	public void WriteLine<T>(T value) { file.WriteLine(value); }
	public void WriteLine(string str, params object[] args) { file.WriteLine(str, args); }
	public void Dispose() { file.Flush(); }
}
class Scanner : IDisposable
{
	private TextReader file;
	public Scanner() { file = Console.In; }
	public Scanner(string path) { file = new StreamReader(path); }
	public void Dispose() { if (file != Console.In) file.Dispose(); }
	public T Get<T>() { return (T)Convert(file.ReadLine(), Type.GetTypeCode(typeof(T))); }
	public Tuple<S, T> Get<S, T>() { S s; T t; Read(out s, out t); return new Tuple<S, T>(s, t); }
	public Tuple<S, T, U> Get<S, T, U>() { S s; T t; U u; Read(out s, out t, out u); return new Tuple<S, T, U>(s, t, u); }
	public Tuple<S, T, U, V> Get<S, T, U, V>() { S s; T t; U u; V v; Read(out s, out t, out u, out v); return new Tuple<S, T, U, V>(s, t, u, v); }
	public Pair<S, T> Pair<S, T>() { S s; T t; Read(out s, out t); return new Pair<S, T>(s, t); }
	private object Convert(string str, TypeCode type)
	{
		if (type == TypeCode.Int32) return int.Parse(str);
		else if (type == TypeCode.UInt32) return uint.Parse(str);
		else if (type == TypeCode.Int64) return long.Parse(str);
		else if (type == TypeCode.UInt64) return ulong.Parse(str);
		else if (type == TypeCode.Double) return double.Parse(str);
		else if (type == TypeCode.Decimal) return decimal.Parse(str);
		else if (type == TypeCode.String) return str;
		else throw new Exception();
	}
	public T[] ReadMany<T>(int n) { var type = Type.GetTypeCode(typeof(T)); return file.ReadLine().Split().Select(str => (T)Convert(str, type)).ToArray(); }
	public T[] ReadManyLines<T>(int n, Func<T> selector) { return Enumerable.Range(0, n).Select(_ => selector()).ToArray(); }
	public T[] ReadManyLines<T>(int n) { return Enumerable.Range(0, n).Select(_ => Get<T>()).ToArray(); }
	public Tuple<S, T>[] ReadManyLines<S, T>(int n) { return Enumerable.Range(0, n).Select(_ => Get<S, T>()).ToArray(); }
	public Tuple<S, T, U>[] ReadManyLines<S, T, U>(int n) { return Enumerable.Range(0, n).Select(_ => Get<S, T, U>()).ToArray(); }
	public Tuple<S, T, U, V>[] ReadManyLines<S, T, U, V>(int n) { return Enumerable.Range(0, n).Select(_ => Get<S, T, U, V>()).ToArray(); }
	public void Read<S>(out S s)
	{
		var read = ReadMulti(Type.GetTypeCode(typeof(S))).ToArray();
		s = (S)read[0];
	}
	public void Read<S, T>(out S s, out T t)
	{
		var read = ReadMulti(Type.GetTypeCode(typeof(S)), Type.GetTypeCode(typeof(T))).ToArray();
		s = (S)read[0];
		t = (T)read[1];
	}
	public void Read<S, T, U>(out S s, out T t, out U u)
	{
		var read = ReadMulti(Type.GetTypeCode(typeof(S)), Type.GetTypeCode(typeof(T)), Type.GetTypeCode(typeof(U))).ToArray();
		s = (S)read[0];
		t = (T)read[1];
		u = (U)read[2];
	}
	public void Read<S, T, U, V>(out S s, out T t, out U u, out V v)
	{
		var read = ReadMulti(Type.GetTypeCode(typeof(S)), Type.GetTypeCode(typeof(T)), Type.GetTypeCode(typeof(U)), Type.GetTypeCode(typeof(V))).ToArray();
		s = (S)read[0];
		t = (T)read[1];
		u = (U)read[2];
		v = (V)read[3];
	}
	private IEnumerable<object> ReadMulti(params TypeCode[] types)
	{
		var inp = file.ReadLine().Split();
		for (var i = 0; i < types.Length; i++) yield return Convert(inp[i], types[i]);
	}
	public T[,] Board<T>(int X, int Y, Func<char, int, int, T> selector)
	{
		var array = new T[X, Y];
		for (var y = 0; y < Y; y++)
		{
			var str = Get<string>();
			for (var x = 0; x < X; x++) array[x, y] = selector(str[x], x, y);
		}
		return array;
	}
}
static class Func
{
	public static readonly int Inf = 1073741789;
	public static long FirstBinary(long min, long max, Predicate<long> pred)
	{
		var left = min;
		var right = max;
		while (left < right)
		{
			var mid = (left + right) >> 1;
			if (pred(mid)) right = mid;
			else left = mid + 1;
		}
		return left;
	}
}
class Graph
{
	int V;
	List<Tuple<int, int, int>> edges;
	List<Tuple<int, int>>[] edgesFrom;
	List<Tuple<int, int>>[] edgesTo;
	public List<Tuple<int, int>> EdgeFrom(int from)
	{
		return edgesFrom[from];
	}
	public List<Tuple<int, int>> EdgeTo(int to)
	{
		return edgesTo[to];
	}

	public Graph(int V)
	{
		this.V = V;
		edges = new List<Tuple<int, int, int>>();
		edgesFrom = new List<Tuple<int, int>>[V];
		edgesTo = new List<Tuple<int, int>>[V];
		for (int i = 0; i < V; i++)
		{
			edgesFrom[i] = new List<Tuple<int, int>>();
			edgesTo[i] = new List<Tuple<int, int>>();
		}
	}

	public void Add(int from, int to, int cost)
	{
		var edge = new Tuple<int, int, int>(from, to, cost);
		this.edges.Add(edge);
		edgesFrom[from].Add(new Tuple<int, int>(to, cost));
		edgesTo[to].Add(new Tuple<int, int>(from, cost));
	}

	public int[] BellmanFord(int start)
	{
		var d = new int[V];
		for (int v = 0; v < V; v++)
		{
			d[v] = Func.Inf;
		}
		d[start] = 0;
		for (int i = 0; i < V; i++)
		{
			foreach (var e in edges)
			{
				if (d[e.Item1] != Func.Inf && d[e.Item2] > d[e.Item1] + e.Item3)
				{
					d[e.Item2] = d[e.Item1] + e.Item3;
					if (i == V - 1) return null;
				}
			}
		}
		return d;
	}

	public int[] Dijkstra(int start)
	{
		var que = new PriorityQueue<Tuple<int, int>>((x, y) => x.Item1.CompareTo(y.Item1));
		var d = new int[V];
		for (int v = 0; v < V; v++)
		{
			d[v] = Func.Inf;
		}
		d[start] = 0;
		que.Enqueue(new Tuple<int, int>(0, start));

		while (que.Count > 0)
		{
			var p = que.Dequeue();
			int v = p.Item2;
			if (d[v] < p.Item1) continue;
			foreach (var e in EdgeFrom(p.Item2))
			{
				if (d[e.Item1] > d[v] + e.Item2)
				{
					d[e.Item1] = d[v] + e.Item2;
					que.Enqueue(new Tuple<int, int>(d[e.Item1], e.Item1));
				}

			}
		}
		return d;
	}

	public int[,] WarshallFloyd()
	{
		var d = new int[V, V];
		for (int from = 0; from < V; from++)
		{
			for (int to = 0; to < V; to++)
			{
				d[from, to] = Func.Inf;
				if (from == to)
					d[from, to] = 0;
			}
		}
		foreach (var e in edges)
		{
			d[e.Item1, e.Item2] = Math.Min(d[e.Item1, e.Item2], e.Item3);
		}
		for (int k = 0; k < V; k++)
		{
			for (int i = 0; i < V; i++)
			{
				for (int j = 0; j < V; j++)
				{
					d[i, j] = Math.Min(d[i, j], d[i, k] + d[k, j]);
				}
			}
		}
		return d;
	}
}
class UnionFindTree
{
	int[] Par;
	int[] Rank;
	public UnionFindTree(int n)
	{
		Par = new int[n];
		Rank = new int[n];
		for (int i = 0; i < n; i++)
		{
			Par[i] = i;
			Rank[i] = 0;
		}
	}

	public int Find(int x) { return Par[x] == x ? x : Par[x] = Find(Par[x]); }

	public void Unite(int x, int y)
	{
		x = Find(x);
		y = Find(y);
		if (x == y) return;

		if (Rank[x] < Rank[y]) Par[x] = y;
		else { Par[y] = x; if (Rank[x] == Rank[y]) Rank[x]++; }
	}

	public bool IsSame(int x, int y) { return Find(x) == Find(y); }
	public void Print(Printer pr)
	{
		Console.Clear();
		for (int i = 0; i < Par.Length; i++)
		{
			pr.WriteLine("{0} -> {1}", i, Par[i]);
		}
	}

}
class PriorityQueue<T>
{
	List<T> heap;
	int sz;
	Comparison<T> comp;
	public PriorityQueue() : this((x, y) => ((IComparable<T>)(x)).CompareTo(y)) { }
	public PriorityQueue(Comparison<T> comp)
	{
		heap = new List<T>();
		sz = 0;
		this.comp = comp;
	}
	public int Count { get { return sz; } }

	public void Enqueue(T x)
	{
		int i = sz++;
		if (sz > heap.Count) heap.Add(default(T));

		while (i > 0)
		{
			int p = (i - 1) / 2;
			if (comp(heap[p], x) <= 0) break;
			heap[i] = heap[p];
			i = p;
		}
		heap[i] = x;
	}
	public T Peek()
	{
		return heap[0];
	}
	public T Dequeue()
	{
		if (sz == 0) throw new InvalidOperationException("空のヒープからポップすることは出来ません。");
		T ret = heap[0];
		T x = heap[--sz];

		int i = 0;
		while (i * 2 + 1 < sz)
		{
			int a = i * 2 + 1, b = i * 2 + 2;
			if (b < sz && comp(heap[b], heap[a]) < 0) a = b;

			if (comp(heap[a], x) >= 0) break;

			heap[i] = heap[a];
			i = a;
		}

		heap[i] = x;

		return ret;
	}
}

提出情報

提出日時
問題 D - へんてこ辞書
ユーザ pythagorean
言語 C# (Mono 3.2.1.0)
得点 100
コード長 11349 Byte
結果 AC
実行時間 233 ms
メモリ 25276 KiB

ジャッジ結果

セット名 Sample Subtask1 All
得点 / 配点 0 / 0 50 / 50 50 / 50
結果
AC × 2
AC × 12
AC × 25
セット名 テストケース
Sample subtask0_sample_01.txt, subtask0_sample_03.txt
Subtask1 subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask0_sample_01.txt, subtask0_sample_03.txt
All subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask0_sample_01.txt, subtask0_sample_03.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt, subtask1_sample_02.txt
ケース名 結果 実行時間 メモリ
subtask0_0.txt AC 218 ms 22784 KiB
subtask0_1.txt AC 209 ms 22032 KiB
subtask0_2.txt AC 215 ms 22408 KiB
subtask0_3.txt AC 193 ms 17468 KiB
subtask0_4.txt AC 226 ms 24976 KiB
subtask0_5.txt AC 204 ms 21892 KiB
subtask0_6.txt AC 186 ms 17504 KiB
subtask0_7.txt AC 212 ms 22420 KiB
subtask0_8.txt AC 191 ms 17456 KiB
subtask0_9.txt AC 216 ms 22660 KiB
subtask0_sample_01.txt AC 146 ms 9884 KiB
subtask0_sample_03.txt AC 144 ms 9884 KiB
subtask1_0.txt AC 194 ms 18620 KiB
subtask1_1.txt AC 211 ms 23056 KiB
subtask1_10.txt AC 233 ms 24204 KiB
subtask1_11.txt AC 144 ms 9872 KiB
subtask1_2.txt AC 189 ms 18104 KiB
subtask1_3.txt AC 193 ms 16860 KiB
subtask1_4.txt AC 191 ms 17604 KiB
subtask1_5.txt AC 214 ms 23444 KiB
subtask1_6.txt AC 187 ms 17324 KiB
subtask1_7.txt AC 182 ms 16440 KiB
subtask1_8.txt AC 221 ms 24996 KiB
subtask1_9.txt AC 220 ms 25276 KiB
subtask1_sample_02.txt AC 145 ms 9884 KiB