brute force implementation math two pointers *1600

Please click on ads to support us..

Python Code:

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    pos = [0 for i in range(n+1)]
    neg = [0 for j in range(n+1)]
    for i in range(n):
        if a[i] > 0:
            if pos[i] > 0:
                if a[i] == 1:
                    pos[i+1] = pos[i]
                else:
                    pos[i+1] = pos[i] + 1
            else:
                if a[i] == 1:
                    pos[i+1] = 1
                else:
                    pos[i+1] = 2

            if neg[i] < 0:
                if a[i] == 1:
                    neg[i+1] = neg[i]
                else:
                    neg[i+1] = neg[i] - 1
        elif a[i] < 0:
            if neg[i] == 0:
                pos[i+1] = 0
            else:
                if a[i] == -1:
                    pos[i+1] = abs(neg[i])
                else:
                    pos[i+1] = abs(neg[i]) + 1

            if pos[i] == 0:
                neg[i+1] = a[i]
            else:
                if a[i] == -1:
                    neg[i+1] = -pos[i]
                else:
                    neg[i+1] = -(pos[i] + 1)
    best = 1
    best_index = -1
    for i in range(1, n+1):
        if pos[i] > best:
            best = pos[i]
            best_index = i
    if best == 1 or best_index == -1:
        print(n, 0)
    else:
        last_part = n - best_index
        sign = 0         twos_required = best - 1
        twos_seen = 0
        for i in range(best_index, 0, -1):
            if abs(a[i-1]) == 2:
                twos_seen += 1
            if a[i-1] < 0:
                if sign == 1:
                    sign = 0
                else:
                    sign = 1
            if twos_seen == twos_required and sign == 0:
                first_part = i
                break
        print(first_part - 1, last_part)

C++ Code:

#include <bits/stdc++.h>

#define IN cin
#define OUT cout

using namespace std;

#define FOR(a,b,c) for(int a=b; a < c; a++)


int T;
int N;
vector<int> A;
vector<int> C2;

int FindNextNonZero(int pos)
{
	FOR(i,pos,N)
	{
		assert(i >= 0 && i < N);
		if(A[i] != 0)
			return i;
	}
	return -1;
}

int FindNextZero(int pos)
{
	FOR(i,pos,N)
	{
		assert(i >= 0 && i < N);		
		if(A[i] == 0)
			return i;
	}
	return -1;
}

pair<int, pair<int, int>> comp(int lower, int upper)
{
	if(lower == upper)
	{
		if(A[lower] == 2)
			return {1, {lower, N-1-lower}};
		else
			return {0,{-1,-1}};
	}
	
	assert(lower >= 0 && upper < N && lower <= upper);
	int neg_count = 0;
	int first_neg = -1;
	int last_neg = -1;
	for(int i = lower; i <= upper; i++)
	{
		assert(i >= 0 && i < N);
		if(A[i] < 0)
		{
			neg_count++;
			last_neg = i;
		}
	}
	for(int i=lower; i <= upper; i++)
	{
		assert(i >= 0 && i < N);
		if(A[i] < 0)
		{
			first_neg = i;
			break;
		}
	}
	if(neg_count % 2 == 0)
	{
		int prod;
		if(lower > 0)
			prod = C2[upper] - C2[lower-1];
		else
			prod = C2[upper];
		
		return {prod, {lower, N-upper-1}};
	}
	

	
	int left_prod = 0;
	if(lower > 0 && last_neg > 0)
		left_prod = C2[last_neg-1] - C2[lower -1];
	else if(last_neg > 0)
		left_prod = C2[last_neg-1];
	
	
	int right_prod = C2[upper] - C2[first_neg];
	
	
	if(right_prod > left_prod)
	{
	
		return {right_prod,{first_neg + 1, N-upper-1}};
	}
	
	return {left_prod,{lower, N-last_neg}};
}


pair<int, int> solve()
{
	A = vector<int>(N);
	C2 = vector<int>(N);
	FOR(n,0,N)
	{
		IN >> A[n];
		if(n == 0)
		{
			C2[0] = (A[n] == -2 || A[n] == 2);
		} else
		{
			C2[n] = C2[n-1] + (A[n] == -2 || A[n] == 2);
		}
	}
	
	int first_nonzero = FindNextNonZero(0);
	if(first_nonzero == -1)
		return {N, 0};
	
	int index = first_nonzero;
	vector<pair<int, int>> Q;
	while(index < N)
	{
		int next_zero = FindNextZero(index);
		if(next_zero == -1)
		{
			Q.push_back({index, N-1});
			break;
		} else
		{
			Q.push_back({index, next_zero -1});
		}
		index = FindNextNonZero(next_zero + 1);
		if(index == -1)
			break;
	}
	

	int prod = 0;
	pair<int, int> ans = {N,0};
	for(auto [l, u] : Q)
	{
		auto [a, p] = comp(l,u);
		if(a > prod)
		{
			ans = p;
			prod = a;
		}
		
	}
	
	return ans;
}


int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ////////////////////////
    ////////////////////////
	
	IN >> T;
	FOR(t,0,T)
	{
		IN >> N;
		auto [x,y] = solve();
		OUT << x << " " << y << "\n";
	
	}
	OUT << flush;
}


Comments

Submit
0 Comments
More Questions

1114A - Got Any Grapes
224B - Array
125B - Simple XML
567B - Berland National Library
431B - Shower Line
282C - XOR and OR
1582B - Luntik and Subsequences
609A - Флеш-карты
1207A - There Are Two Types Of Burgers
371C - Hamburgers
343B - Alternating Current
758B - Blown Garland
1681B - Card Trick
1592A - Gamer Hemose
493D - Vasya and Chess
1485A - Add and Divide
337B - Routine Problem
1392D - Omkar and Bed Wars
76E - Points
762C - Two strings
802M - April Fools' Problem (easy)
577B - Modulo Sum
1555B - Two Tables
1686A - Everything Everywhere All But One
1469B - Red and Blue
1257B - Magic Stick
18C - Stripe
1203B - Equal Rectangles
1536A - Omkar and Bad Story
1509A - Average Height