Submission #27242

#TimeUsernameProblemLanguageResultExecution timeMemory
27242undecember구간 성분 (KOI15_interval)C++14
30 / 100
349 ms131072 KiB
#include <bits/stdc++.h> using namespace std; class dtf { public: long long int hash; int len; dtf() : len(0), hash(0) {} dtf(int _l, int _h) : len(_l), hash(_h) {} }; string a, b; vector<dtf> dha, dhb; long long int ha[1505][1505], hb[1505][1505]; const int PRIME = 1511; void mkh(string &s, long long int (*arr)[1505], vector<dtf> &v); bool cmph(dtf a, dtf b); bool cmpl(dtf a, dtf b) { return a.len > b.len; } int main(void) { cin >> a >> b; if (a.length() > b.length()) swap(a, b); mkh(a, ha, dha); mkh(b, hb, dhb); sort(dha.begin(), dha.end(), cmpl); sort(dhb.begin(), dhb.end(), cmph); int ans = 0; for (auto av : dha) { bool flag = binary_search(dhb.begin(), dhb.end(), av, cmph); if (flag) { ans = av.len; break; } } printf("%d", ans); return 0; } void mkh(string &s, long long int (*arr)[1505], vector<dtf> &v) { for (int i = 0; i < s.length(); i++) { for (int j = i; j < s.length(); j++) { long long int p = 1; for (int k = 'a'; k < s[j]; k++) p *= PRIME; arr[i][j] += p; arr[i][j + 1] = arr[i][j]; v.push_back(dtf(j - i + 1, arr[i][j])); } } } bool cmph(dtf a, dtf b) { if (a.hash < b.hash) return true; if (a.hash > b.hash) return false; return a.len < b.len; }

Compilation message (stderr)

interval.cpp: In constructor 'dtf::dtf()':
interval.cpp:9:6: warning: 'dtf::len' will be initialized after [-Wreorder]
  int len;
      ^
interval.cpp:8:16: warning:   'long long int dtf::hash' [-Wreorder]
  long long int hash;
                ^
interval.cpp:10:2: warning:   when initialized here [-Wreorder]
  dtf() : len(0), hash(0) {}
  ^
interval.cpp: In constructor 'dtf::dtf(int, int)':
interval.cpp:9:6: warning: 'dtf::len' will be initialized after [-Wreorder]
  int len;
      ^
interval.cpp:8:16: warning:   'long long int dtf::hash' [-Wreorder]
  long long int hash;
                ^
interval.cpp:11:2: warning:   when initialized here [-Wreorder]
  dtf(int _l, int _h) : len(_l), hash(_h) {}
  ^
interval.cpp: In function 'void mkh(std::__cxx11::string&, long long int (*)[1505], std::vector<dtf>&)':
interval.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.length(); i++)
                    ^
interval.cpp:52:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i; j < s.length(); j++)
                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...