結果

問題 No.515 典型LCP
ユーザー vvataarne
提出日時 2017-05-05 23:40:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,785 bytes
コンパイル時間 2,030 ms
コンパイル使用メモリ 178,064 KB
実行使用メモリ 166,580 KB
最終ジャッジ日時 2024-09-14 09:20:35
合計ジャッジ時間 6,612 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

// clang-format off

#include <bits/stdc++.h>

#define int long long int
#define main signed main()
#define bye return 0
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define each(p, v) for (auto p = (v).begin(); p != (v).end(); p++)
#define all(v) (v).begin(), (v).end()
#define prec(n) fixed << setprecision(n)
#define dump(x) cerr << "(L" << __LINE__ << ") " << #x << " = " << (x) << endl
#define clr(x, a) memset(x, a, sizeof(x))

#define sum(v) accumulate(all(v), 0)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define odd(n) ((n) % 2)
#define even(n) (!odd(n))

#define INF 1000000000
#define MOD 1000000007

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>

using namespace std;

// clang-format on

/*
for k in 1 .. M
  i[k] = (x / (n - 1)) + 1
  j[k] = (x % (n - 1)) + 1
  if (i[k] > j[k])
    swap(i[k], j[k])
  else
    j[k] = j[k] + 1
  end
  x = (x + d) % (n * (n - 1))
end
*/

map<pair<int, int>, int> p;

main {
  int n;
  cin >> n;
  string s[n];
  rep(i, n) cin >> s[i];
  int m, x, d;
  cin >> m >> x >> d;
  int i[m], j[m];
  rep(k, m) {
    i[k] = (x / (n - 1)) + 1;
    j[k] = (x % (n - 1)) + 1;
    if (i[k] > j[k]) {
      swap(i[k], j[k]);
    } else {
      j[k] = j[k] + 1;
    }
    x = (x + d) % (n * (n - 1));
  }
  int c = 0;
  rep(k, m) {
    if (p.count(mp(i[k], j[k]))) {
      c += p[mp(i[k], j[k])];
      continue;
    }
    string a = s[i[k] - 1], b = s[j[k] - 1];
    int q = 0;
    rep(l, min(a.size(), b.size())) {
      if (a[l] == b[l]) {
        q++;
      } else {
        break;
      }
    }
    p[mp(i[k], j[k])] = q;
    c += q;
  }
  cout << c << endl;
  bye;
}
0