Submission #751616

#	Time	Username	Problem	Language	Result	Execution time	Memory
751616		rxlfd314	Sequence (APIO23_sequence)	C++17	35 / 100	484 ms	31560 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;

int sequence(int N, vector<int> A) {
	if (N <= 2000) {
		int ans = 1;
		for (int i = 0; i < N; i++) {
			vector<int> cnt(N+1, 0);
			multiset<ari2> stuff;
			cnt[A[i]]++;
			stuff.insert({A[i], -i});
			ari2 med = {A[i], -i};
			for (int j = i+1; j < N; j++) {
				stuff.insert({A[j], -j});
				cnt[A[j]]++;
				if (ari2{A[j], -j} < med && (j - i & 1)) {
					med = *prev(stuff.find(med));
				} else if (ari2{A[j], -j} > med && !(j - i & 1)) {
					med = *next(stuff.find(med));
				}
				ans = max(ans, cnt[med[0]]);
				if (j - i & 1) {
					auto [a, b] = *next(stuff.find(med));
					ans = max(ans, cnt[a]);
				}
			}
		}
		return ans;
	}
	
	int middle = max_element(A.begin(), A.end()) - A.begin();
	bool mountain = true;	
	for (int i = middle - 1; i >= 0 && mountain; i--) {
		mountain &= A[i] <= A[i+1];
	}
	for (int i = middle + 1; i < N && mountain; i++) {
		mountain &= A[i] <= A[i-1];
	}
	if (mountain) {
		vector<int> inds[N];
		for (int i = 0; i < N; i++) {
			inds[A[i]-1].push_back(i);
		}
		
		int ans = 0;
		for (int ii = 0; ii < N; ii++) {
			if (inds[ii].size() < 2) {
				ans = max(ans, (int)inds[ii].size());
				continue;
			}
			int l1 = inds[ii][0], r1 = -1, l2 = -1, r2 = inds[ii].back();
			for (int i = 1; i < inds[ii].size(); i++) {
				if (inds[ii][i-1]+1 < inds[ii][i]) {
					r1 = inds[ii][i-1];
					l2 = inds[ii][i];
					break;
				}
			}
			if (r1 < 0) {
				ans = max(ans, r2 - l1 + 1);
			} else {
				int gap = l2 - r1 - 1;
				if (gap > r1 - l1 + 1 + r2 - l2 + 1) {
					if (l1 + N - r2 - 1 >= gap - (r1 - l1 + 1 + r2 - l2 + 1)) {
						ans = max(ans, r1 - l1 + 1 + r2 - l2 + 1);
					}
				} else {
					ans = max(ans, r1 - l1 + 1 + r2 - l2 + 1);
				}
				ans = max({ans, r1 - l1 + 1, r2 - l2 + 1});
			}
		}
		
		return ans;
	}
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:18:36: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |     if (ari2{A[j], -j} < med && (j - i & 1)) {
      |                                  ~~^~~
sequence.cpp:20:44: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   20 |     } else if (ari2{A[j], -j} > med && !(j - i & 1)) {
      |                                          ~~^~~
sequence.cpp:24:11: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   24 |     if (j - i & 1) {
      |         ~~^~~
sequence.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for (int i = 1; i < inds[ii].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
sequence.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
   78 | }
      | ^

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 7 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18