oj.uz

Submission #27244

# Submission time Handle Problem Language Result Execution time Memory
27244 2017-07-11T13:01:32 Z undecember 구간 성분 (KOI15_interval) C++14
100 / 100
 989 ms 118112 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19720 KB Output is correct
2 Correct 0 ms 19860 KB Output is correct
3 Correct 6 ms 20060 KB Output is correct
4 Correct 3 ms 20060 KB Output is correct
5 Correct 3 ms 20060 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 25952 KB Output is correct
2 Correct 39 ms 25948 KB Output is correct
3 Correct 33 ms 25952 KB Output is correct
4 Correct 29 ms 25952 KB Output is correct
5 Correct 66 ms 25952 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 44384 KB Output is correct
2 Correct 393 ms 44384 KB Output is correct
3 Correct 386 ms 44384 KB Output is correct
4 Correct 349 ms 44384 KB Output is correct
5 Correct 363 ms 44384 KB Output is correct
6 Correct 336 ms 44384 KB Output is correct
7 Correct 349 ms 44384 KB Output is correct
8 Correct 313 ms 44384 KB Output is correct
9 Correct 306 ms 44384 KB Output is correct
10 Correct 336 ms 44384 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 68960 KB Output is correct
2 Correct 849 ms 118112 KB Output is correct
3 Correct 693 ms 118112 KB Output is correct
4 Correct 349 ms 118112 KB Output is correct
5 Correct 989 ms 118112 KB Output is correct