oj.uz

Submission #298453

# Submission time Handle Problem Language Result Execution time Memory
298453 2020-09-12T21:26:15 Z peuch Necklace (Subtask 1-3) (BOI19_necklace1) C++17
0 / 85
 17 ms 384 KB 
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 410;

char st1[MAXN];
char st2[MAXN];

int prefix[MAXN];
int sufix[MAXN];

int ans;
pair<int, int> pos;

int n1, n2;

int main(){
	scanf(" %s", st1);
	scanf(" %s", st2);
	n1 = strlen(st1);
	n2 = strlen(st2);
	for(int i = 0; i < n1; i++){
		for(int j = 1; j < n1; j++)
			swap(st1[j - 1], st1[j]);

		for(int j = 0; j < n2; j++){
			prefix[j] = 0;
			sufix[j] = 0;
			for(int k = 0; k < min(n1, n2); k++){
				if(st1[k] == st2[(j + k) % n2]) prefix[j]++;
				else break;
			}
			for(int k = 0; k < min(n1, n2); k++){
				if(st1[n1 - k - 1] == st2[(j - k + n2) % n2]) sufix[j]++;
				else break;
			}
		}

		// printf("%s\n", st1);
		// printf("%s\n", st2);
		for(int j = 0; j < n2; j++){
			for(int k = (j + prefix[j]) % n2; k != j; k++, k %= n2){
				int aux = (k - j + n2) % n2 + 1;
				if(prefix[j] + sufix[k] >= aux) ans = max(ans, min(aux, min(n1, n2)));
			}
			// printf("\tp[%d] = %d, s[%d] = %d\n", j, prefix[j], j, sufix[j]);
		}
	}

	reverse(st2, st2 + n2);

	for(int i = 0; i < n1; i++){
		for(int j = 1; j < n1; j++)
			swap(st1[j - 1], st1[j]);

		for(int j = 0; j < n2; j++){
			prefix[j] = 0;
			sufix[j] = 0;
			for(int k = 0; k < min(n1, n2); k++){
				if(st1[k] == st2[(j + k) % n2]) prefix[j]++;
				else break;
			}
			for(int k = 0; k < min(n1, n2); k++){
				if(st1[n1 - k - 1] == st2[(j - k + n2) % n2]) sufix[j]++;
				else break;
			}
		}

		// printf("%s\n", st1);
		// printf("%s\n", st2);
		for(int j = 0; j < n2; j++){
			for(int k = (j + prefix[j]) % n2; k != j; k++, k %= n2){
				int aux = (k - j + n2) % n2 + 1;
				if(prefix[j] + sufix[k] >= aux) ans = max(ans, min(aux, min(n1, n2)));
			}
			// printf("\tp[%d] = %d, s[%d] = %d\n", j, prefix[j], j, sufix[j]);
		}
	}
	printf("%d\n", ans);
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |  scanf(" %s", st1);
      |  ~~~~~^~~~~~~~~~~~
necklace.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |  scanf(" %s", st2);
      |  ~~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 384 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 384 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 384 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -