結果
| 問題 | No.515 典型LCP |
| ユーザー |
 くれちー
|
| 提出日時 | 2017-07-27 16:50:16 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,739 bytes |
| コンパイル時間 | 1,070 ms |
| コンパイル使用メモリ | 111,872 KB |
| 実行使用メモリ | 37,504 KB |
| 最終ジャッジ日時 | 2024-04-18 08:52:21 |
| 合計ジャッジ時間 | 5,554 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using static System.Console;
using static System.Convert;
using static System.Math;
using static Extentions;
class IO
{
int idx;
string[] input;
public IO(TextReader reader)
{
input = reader.ReadToEnd().Split(new[] { " ", "\n", "\r" },
StringSplitOptions.RemoveEmptyEntries);
}
T Get<T>(Func<string, T> parser) => parser(input[idx++]);
public string S => Get(s => s);
public char C => Get(char.Parse);
public int I => Get(int.Parse);
public long L => Get(long.Parse);
public double F => Get(double.Parse);
public decimal D => Get(decimal.Parse);
public BigInteger B => Get(BigInteger.Parse);
T[] Gets<T>(int n, Func<string, T> parser)
=> input.Skip((idx += n) - n).Take(n).Select(parser).ToArray();
public string[] Ss(int n) => Gets(n, s => s);
public char[] Cs(int n) => Gets(n, char.Parse);
public int[] Is(int n) => Gets(n, int.Parse);
public long[] Ls(int n) => Gets(n, long.Parse);
public double[] Fs(int n) => Gets(n, double.Parse);
public decimal[] Ds(int n) => Gets(n, decimal.Parse);
public BigInteger[] Bs(int n) => Gets(n, BigInteger.Parse);
public void Write<T>(params T[] xs) => WriteLine(string.Join(" ", xs));
public void Write(params object[] xs) => WriteLine(string.Join(" ", xs));
}
#region http://qiita.com/Camypaper/items/de6d576fe5513743a50e
public class StreamScanner
{
public StreamScanner(Stream stream) { str = stream; }
private readonly Stream str;
private readonly byte[] buf = new byte[1024];
private int len, ptr;
public bool isEof = false;
public bool IsEndOfStream { get { return isEof; } }
private byte read()
{
if (isEof) throw new EndOfStreamException();
if (ptr >= len)
{
ptr = 0;
if ((len = str.Read(buf, 0, 1024)) <= 0)
{
isEof = true;
return 0;
}
}
return buf[ptr++];
}
public char Char()
{
byte b = 0;
do b = read();
while (b < 33 || 126 < b);
return (char)b;
}
public string Scan()
{
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
sb.Append(b);
return sb.ToString();
}
public long Long()
{
long ret = 0; byte b = 0; var ng = false;
do b = read();
while (b != '-' && (b < '0' || '9' < b));
if (b == '-') { ng = true; b = read(); }
for (; true; b = read())
{
if (b < '0' || '9' < b)
return ng ? -ret : ret;
else ret = ret * 10 + b - '0';
}
}
public int Integer() { return (int)Long(); }
public double Double() { return double.Parse(Scan(), System.Globalization.CultureInfo.InvariantCulture); }
}
#endregion
class SparseTable
{
int[] xs, logTable;
int[,] table;
int n;
public SparseTable(int[] xs)
{
n = xs.Length;
this.xs = xs;
logTable = new int[n + 1];
for (var i = 2; i <= n; i++) logTable[i] = logTable[i >> 1] + 1;
table = new int[n, logTable[n] + 1];
for (var i = 0; i < n; i++) table[i, 0] = i;
for (var k = 1; (1 << k) < n; k++)
{
for (var i = 0; i + (1 << k) <= n; i++)
{
var a = table[i, k - 1];
var b = table[i + (1 << (k - 1)), k - 1];
table[i, k] = xs[a] < xs[b] ? a : b;
}
}
}
public int Query(int i, int j)
{
var k = logTable[j - i];
return Min(xs[table[i, k]], xs[table[j - (1 << k) + 1, k]]);
}
}
static class Extentions
{
public static void Swap<T>(ref T x, ref T y)
{
var tmp = x;
x = y;
y = tmp;
}
}
static class Program
{
public static void Main()
{
var sw = new StreamWriter(OpenStandardOutput()) { NewLine = "\n" };
#if DEBUG
sw.AutoFlush = true;
#else
sw.AutoFlush = false;
#endif
SetOut(sw);
Solve(new StreamScanner(OpenStandardInput()));
Out.Flush();
}
static int Lcp(string a, string b)
{
var cnt = 0;
var len = Min(a.Length, b.Length);
for (var i = 0; i < len; i++) if (a[i] == b[i]) cnt++; else break;
return cnt;
}
static void Solve(StreamScanner sc)
{
var n = sc.Integer();
var s = new string[n];
for (var i = 0; i < n; i++) s[i] = sc.Scan();
var m = sc.Integer();
var x = sc.Long();
var d = sc.Long();
var bsi = new int[n];
var asi = new int[n];
for (var i = 0; i < n; i++) bsi[i] = asi[i] = i;
Array.Sort(bsi, (a, b) => s[a].CompareTo(s[b]));
Array.Sort(asi, (a, b) => bsi[a].CompareTo(bsi[b]));
var ts = new string[n];
for (var i = 0; i < n; i++) ts[i] = s[bsi[i]];
s = ts;
var lcplen = new int[n - 1];
for (var i = 0; i < n - 1; i++) lcplen[i] = Lcp(s[i], s[i + 1]);
var st = new SparseTable(lcplen);
var ans = 0L;
var mod = (long)n * (n - 1);
for (var k = 0; k < m; k++)
{
var i = x / (n - 1);
var j = x % (n - 1);
if (i > j) Swap(ref i, ref j);
else j++;
var p = asi[i];
var q = asi[j];
if (p > q) Swap(ref p, ref q);
var t = st.Query(p, q - 1);
ans += t;
x = (x + d) % mod;
}
WriteLine(ans);
}
}