結果

問題 No.515 典型LCP
ユーザー claw88claw88
提出日時 2017-07-13 12:35:30
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 266 ms / 1,000 ms
コード長 1,925 bytes
コンパイル時間 1,792 ms
コンパイル使用メモリ 106,808 KB
実行使用メモリ 26,096 KB
最終ジャッジ日時 2024-10-07 18:08:19
合計ジャッジ時間 5,139 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 266 ms
26,096 KB
testcase_01 AC 259 ms
26,032 KB
testcase_02 AC 143 ms
20,580 KB
testcase_03 AC 5 ms
12,432 KB
testcase_04 AC 6 ms
12,212 KB
testcase_05 AC 99 ms
18,452 KB
testcase_06 AC 100 ms
20,176 KB
testcase_07 AC 99 ms
18,648 KB
testcase_08 AC 133 ms
18,356 KB
testcase_09 AC 102 ms
21,188 KB
testcase_10 AC 102 ms
23,388 KB
testcase_11 AC 104 ms
23,292 KB
testcase_12 AC 103 ms
23,896 KB
testcase_13 AC 104 ms
18,900 KB
testcase_14 AC 27 ms
19,968 KB
testcase_15 AC 100 ms
16,092 KB
testcase_16 AC 98 ms
16,448 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec; typedef pair<string, int> pi;
int dd[] = { 0, 1, 0, -1, 0 };

int N;
pi P[114514];
string S[114514];
int ID[114514];
#define M 200010
#define K 18
int st[K][M];
int lcp[114514];

void construct(int *a, int n)
{
	copy_n(a, n, st[0]);
	for (int k = 1; k < K; k++)
	{
		for (int i = 0; i + (1 << k) <= n; i++)
		{
			st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
		}
	}
}
int query(int a, int b)
{
	int k = 31 - __builtin_clz(b - a);
	return min(st[k][a], st[k][b - (1 << k)]);
}
int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> S[i];
		P[i] = { S[i] , i };
	}
	sort(P, P + N);
	sort(S, S + N);
	for (int i = 0; i < N; i++)
	{
		ID[P[i].second] = i;
	}
	for(int i=1;i<N;i++)
	{
		int cnt = 0;
		for(int j=0;j<S[i-1].size()&&j<S[i].size();j++)
		{
			if(S[i-1][j]==S[i][j])cnt++;
			else break;
		}
		lcp[i-1]=cnt;
	}
	construct(lcp, N-1);
	
	/*for(int i = 0; i < N; i++)
	{
		cout << ID[i] << " " << P[i].second << endl;;
	}
	cout << endl;
	/*
	for(int j = 0; j < 4; j++)
	{
		for(int i = 0; i < N - 1; i++)
		{
			cout << st[j][i] << " ";
		}
		cout << endl;
	}*/
	
	int W; i64 x, d;
	cin >> W >> x >> d;
	i64 ans = 0;
	for(int i =0; i<W;i++)
	{
		int P = x / (N-1);
		int Q = x % (N-1);
		if(P>Q) swap(P,Q);
		else Q++;
		
		int  a = ID[P];
		int  b = ID[Q];
		if(a> b)swap(a, b);
		
		//cout << P << " " << Q << endl;
		//cout << a << " " << b << endl;
		ans += query(a,b);
		//cout << ans << endl;
		x = (x +d)% ((i64)N * (N-1));
	}
	cout << ans << endl;

	return 0;
}
0