oj.uz

Submission #921048

# Submission time Handle Problem Language Result Execution time Memory
921048 2024-02-03T09:11:03 Z shoryu386 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
5 / 85
 1500 ms 916 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MOD 1'000'000'007LL
#define MAX 200'007


main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	string a, b; cin >> a >> b;
	
	int n = a.size(), m = b.size();
	
	int ans = -1;
	int resA, resB;
	
	for (int x = 0; x < n; x++){
		for (int y = x; y < n; y++){
			
			string hmm;
			for (int z = x; z <= y; z++) hmm.push_back(a[z]);
			
			unordered_set<string> hash;
			
			hash.insert(hmm);
			for (int x = 0; x < hmm.size(); x++){
				rotate(hmm.begin(),  hmm.begin()+1, hmm.end());
				hash.insert(hmm);
			}
			
			reverse(hmm.begin(), hmm.end());
			hash.insert(hmm);
			for (int x = 0; x < hmm.size(); x++){
				rotate(hmm.begin(), hmm.begin()+1, hmm.end());
				hash.insert(hmm);
			}
			
			string cur = "";
			
			for (int z = 0; z <= (y-x); z++){
				cur.push_back(b[z]);
			}
			
			if (cur == hmm){
				if (ans < (y-x+1)){
					ans = y-x+1;
					resA = x, resB = 0;
				}
			}
			
			for (int z = 1; z+(y-x) < m; z++){
				//cur.pop_front();
				cur.erase(cur.begin()); //slow
				cur.push_back(b[z+y-x]);
				
				if (hash.count(cur)){
					if (ans < (y-x+1)){
						ans = y-x+1;
						resA = x, resB = z;
					}
				}
			}
		}
	}
	
	cout << ans << '\n';
	cout << resA << ' ' << resB;
}

Compilation message

necklace.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main(){
      | ^~~~
necklace.cpp: In function 'int main()':
necklace.cpp:28:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for (int x = 0; x < hmm.size(); x++){
      |                    ~~^~~~~~~~~~~~
necklace.cpp:35:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for (int x = 0; x < hmm.size(); x++){
      |                    ~~^~~~~~~~~~~~

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 488 KB Output is correct
2 Partially correct 48 ms 492 KB Output is partially correct
3 Correct 29 ms 348 KB Output is correct
4 Correct 55 ms 348 KB Output is correct
5 Correct 58 ms 596 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 488 KB Output is correct
2 Partially correct 48 ms 492 KB Output is partially correct
3 Correct 29 ms 348 KB Output is correct
4 Correct 55 ms 348 KB Output is correct
5 Correct 58 ms 596 KB Output is correct
6 Execution timed out 1509 ms 916 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 488 KB Output is correct
2 Partially correct 48 ms 492 KB Output is partially correct
3 Correct 29 ms 348 KB Output is correct
4 Correct 55 ms 348 KB Output is correct
5 Correct 58 ms 596 KB Output is correct
6 Execution timed out 1509 ms 916 KB Time limit exceeded
7 Halted 0 ms 0 KB -