oj.uz

Submission #298420

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

const int MAXN = 3010;

char st1[MAXN];
char st2[MAXN];
int tam1, tam2;
int dp[2][MAXN];
int ans;
pair<int, int> pos;
int n;

int fazDP(int i, int j, int ini, int fim, int cnt);

int main(){
	scanf(" %s", st1);
	scanf(" %s", st2);
	tam1 = strlen(st1);
	tam2 = strlen(st2);
	bool flag = 0;
	if(tam2 < tam1){
		flag = 1;
		swap(st1, st2);
		swap(tam1, tam2);
	}
	for(int i = 0; i < tam1; i++){
		for(int j = 1; j < tam1; j++)
			swap(st1[j], st1[j - 1]);
		for(int j = 0; j < tam2; j++){
			dp[0][j] = 0;
			dp[1][j] = 0;
			for(int k = 0; k < tam1; k++){
				if(st1[k] == st2[(j + k) % tam2]) dp[0][j]++;
				else break;
			}
			for(int k = 0; k < tam1; k++){
				if(st1[tam1 - k - 1] == st2[(j - k + tam2) % tam2]) dp[1][j]++;
				else break;
			}
		}
		for(int j = 0; j < tam2; j++){
			if(dp[0][j] >= ans) ans = dp[0][j], pos = make_pair(i, j);
			for(int k = 0; k < tam2; k++){
				int aux = ((k - j + tam2) % tam2) + 1;
				if(aux <= dp[0][j] || aux > tam1) continue;
				if(dp[0][j] + dp[1][k] >= aux && aux >= ans) ans = aux, pos = make_pair(i - dp[1][k] + 1, j);
			}
		}
	}
	reverse(st2, st2 + tam2);
	for(int i = 0; i < tam1; i++){
		for(int j = 1; j < tam1; j++)
			swap(st1[j], st1[j - 1]);
		for(int j = 0; j < tam2; j++){
			dp[0][j] = 0;
			dp[1][j] = 0;
			for(int k = 0; k < tam1; k++){
				if(st1[k] == st2[(j + k) % tam2]) dp[0][j]++;
				else break;
			}
			for(int k = 0; k < tam1; k++){
				if(st1[tam1 - k - 1] == st2[(j - k + tam2) % tam2]) dp[1][j]++;
				else break;
			}
		}
		for(int j = 0; j < tam2; j++){
			if(dp[0][j] >= ans) ans = dp[0][j], pos = make_pair(i, tam2 - j - dp[0][j]);
			for(int k = 0; k < tam2; k++){
				int aux = ((k - j + tam2) % tam2) + 1;
				if(aux <= dp[0][j] || aux > tam1) continue;
				if(dp[0][j] + dp[1][k] >= aux && aux >= ans) ans = aux, pos = make_pair(i - dp[1][k] + 1, tam2 - k - 1);
			}
		}
	}
	if(flag) swap(pos.first, pos.second);
	printf("%d\n", ans);
	printf("%d %d\n", pos.first, pos.second);
}

Compilation message

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

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 384 KB Output is correct
2 Incorrect 14 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 384 KB Output is correct
2 Incorrect 14 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 384 KB Output is correct
2 Incorrect 14 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -