test/aoj_ALDS1_14_D.cpp

• View this file on GitHub
• Last update: 2024-10-03 22:00:44+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_D

Depends on

• Suffix Array (SA-IS) (string/suffix_array.cpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_D

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

#include "string/suffix_array.cpp"

int main() {
	string T;
	int Q;
	vector<string> P;

	cin >> T >> Q;
	P.resize(Q);
	for(int i = 0; i < Q; i++) cin >> P[i];

	vector<int> sa = SuffixArray(T).get_array();

	auto lb = [&](string &s) {
		int ng = -1, ok = T.length();
		while(ok - ng > 1) {
			int mid = (ok + ng) / 2;
			for(int i = 0; i < s.length(); i++) {
				if(sa[mid] + i >= T.length() or s[i] > T[sa[mid] + i]) {
					ng = mid;
					break;
				}
				if(s[i] < T[sa[mid] + i] or i == s.length() - 1) {
					ok = mid;
					break;
				}
			}
		}
		return ok;
	};

	for(int i = 0; i < Q; i++) {
		int sa_idx = lb(P[i]);
		if(sa_idx >= T.length()) {
			cout << 0 << '\n';
			continue;
		}

		int idx = sa[sa_idx];
		if(idx + P[i].length() > T.length()) {
			cout << 0 << '\n';
			continue;
		}

		cout << (P[i] == T.substr(idx, P[i].length()) ? 1 : 0) << '\n';
	}
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 422, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: test/aoj_ALDS1_14_D.cpp: line 9: found codes out of include guard

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	6 ms	3 MB
g++	01_small_00.in	AC	5 ms	3 MB
g++	01_small_01.in	AC	5 ms	3 MB
g++	02_rand_00.in	AC	5 ms	4 MB
g++	02_rand_01.in	AC	5 ms	3 MB
g++	02_rand_02.in	AC	6 ms	4 MB
g++	03_large_00.in	AC	13 ms	6 MB
g++	03_large_01.in	AC	12 ms	6 MB
g++	03_large_02.in	AC	14 ms	6 MB
g++	03_large_03.in	AC	16 ms	6 MB
g++	03_large_04.in	AC	195 ms	34 MB
g++	03_large_05.in	AC	238 ms	31 MB
g++	04_corner_00.in	AC	6 ms	3 MB
g++	04_corner_01.in	AC	5 ms	3 MB
g++	04_corner_02.in	AC	238 ms	38 MB
g++	04_corner_03.in	AC	246 ms	38 MB
g++	05_maximum_00.in	AC	158 ms	34 MB
g++	05_maximum_01.in	AC	160 ms	34 MB
clang++	00_sample_00.in	AC	6 ms	3 MB
clang++	01_small_00.in	AC	6 ms	3 MB
clang++	01_small_01.in	AC	6 ms	3 MB
clang++	02_rand_00.in	AC	6 ms	4 MB
clang++	02_rand_01.in	AC	6 ms	3 MB
clang++	02_rand_02.in	AC	6 ms	4 MB
clang++	03_large_00.in	AC	13 ms	6 MB
clang++	03_large_01.in	AC	13 ms	6 MB
clang++	03_large_02.in	AC	14 ms	6 MB
clang++	03_large_03.in	AC	16 ms	6 MB
clang++	03_large_04.in	AC	189 ms	34 MB
clang++	03_large_05.in	AC	258 ms	31 MB
clang++	04_corner_00.in	AC	6 ms	3 MB
clang++	04_corner_01.in	AC	5 ms	3 MB
clang++	04_corner_02.in	AC	271 ms	38 MB
clang++	04_corner_03.in	AC	258 ms	38 MB
clang++	05_maximum_00.in	AC	160 ms	34 MB
clang++	05_maximum_01.in	AC	160 ms	35 MB

Back to top page