oj.uz

Submission #27243

# Submission time Handle Problem Language Result Execution time Memory
27243 2017-07-11T12:59:49 Z undecember 구간 성분 (KOI15_interval) C++14
61 / 100
 359 ms 131072 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 ha[1505][1505], hb[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, 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

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 37416 KB Output is correct
2 Correct 0 ms 37556 KB Output is correct
3 Correct 0 ms 37756 KB Output is correct
4 Correct 0 ms 37756 KB Output is correct
5 Correct 0 ms 37756 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 43648 KB Output is correct
2 Correct 39 ms 43644 KB Output is correct
3 Correct 26 ms 43648 KB Output is correct
4 Correct 26 ms 43648 KB Output is correct
5 Correct 66 ms 43648 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 62080 KB Output is correct
2 Correct 316 ms 62080 KB Output is correct
3 Correct 346 ms 62080 KB Output is correct
4 Correct 356 ms 62080 KB Output is correct
5 Correct 346 ms 62080 KB Output is correct
6 Correct 336 ms 62080 KB Output is correct
7 Correct 359 ms 62080 KB Output is correct
8 Correct 339 ms 62080 KB Output is correct
9 Correct 353 ms 62080 KB Output is correct
10 Correct 339 ms 62080 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 86656 KB Output is correct
2 Memory limit exceeded 46 ms 131072 KB Memory limit exceeded
3 Halted 0 ms 0 KB -