oj.uz

Submission #921049

# Submission time Handle Problem Language Result Execution time Memory
921049 2024-02-03T09:11:58 Z shoryu386 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
25 / 85
 1500 ms 848 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 <= (int)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 <= (int)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 (hash.count(cur)){
				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(){
      | ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 348 KB Output is correct
2 Correct 49 ms 348 KB Output is correct
3 Correct 29 ms 344 KB Output is correct
4 Correct 57 ms 500 KB Output is correct
5 Correct 56 ms 480 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 348 KB Output is correct
2 Correct 49 ms 348 KB Output is correct
3 Correct 29 ms 344 KB Output is correct
4 Correct 57 ms 500 KB Output is correct
5 Correct 56 ms 480 KB Output is correct
6 Execution timed out 1535 ms 848 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 348 KB Output is correct
2 Correct 49 ms 348 KB Output is correct
3 Correct 29 ms 344 KB Output is correct
4 Correct 57 ms 500 KB Output is correct
5 Correct 56 ms 480 KB Output is correct
6 Execution timed out 1535 ms 848 KB Time limit exceeded
7 Halted 0 ms 0 KB -