Submission #27244

#	Time	Username	Problem	Language	Result	Execution time	Memory
27244		undecember	구간 성분 (KOI15_interval)	C++14	100 / 100	989 ms	118112 KiB

interval

#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 h[1505][1505];
const int PRIME = 1234567891;

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, h, dha); memset(h, 0, sizeof(h));
	mkh(b, h, 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++)
                     ^

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 31 / 31
• Subtask 4: 39 / 39