Dãy chẵn lẻ cân bằng

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

Small

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy \(A\) gồm \(N\) số nguyên được đánh số từ \(0..N−1\). Hãy tìm một chỉ số \(i\) thỏa mãn điều kiện: dãy trước \(A[i]\) và dãy sau \(A[i]\) thỏa mãn điều kiện: số lượng số chẵn/lẻ trong dãy trước bằng số lượng số chẵn/lẻ trong dãy sau. Nếu tồn tại nhiều chỉ số thỏa mãn điều kiện, in chỉ số có giá trị bé nhất. Nếu không có chỉ số nào thỏa mãn, in \(−1\).

Input

Dòng đầu là chứa số nguyên \(N\) (\(1 \leq N \leq 10^6\)).
Dòng thứ 2 ghi \(N\) số nguyên, các số cách nhau bởi dấu cách.

Output

Ghi chỉ số cần tìm hoặc \(-1\) nếu không tồn tại chỉ số phù hợp.

Example

Test 1

Input

7
4 3 2 1 1 2 4

Output

Test 2

Input

7
1 2 4 5 8 3 12

Output

Bình luận

-1

summary

#include <bits/stdc++.h>
#define int long long
#define BaoDepChai ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define file(f) if(fopen(f".inp", "r")) {freopen(f".INP", "r", stdin); freopen(f".OUT", "w", stdout);}
#define x first
#define y second

using namespace std;

signed main() {

    BaoDepChai

    int n; cin >> n;
    int a[n];
    vector<pair<int, int>> left(n+1);
    vector<pair<int, int>> right(n+1);

    left[0] = {0, 0};
    right[n] = {0, 0};

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        left[i+1].x = left[i].x + (a[i] % 2 == 0);
        left[i+1].y = left[i].y + (a[i] % 2 != 0);
    }

    for (int i = n - 1; i >= 0; --i) {
        right[i].x = right[i+1].x + (a[i] % 2 == 0);
        right[i].y = right[i+1].y + (a[i] % 2 != 0);
    }
    /*for (int i = 0; i <= n; ++i) {
        cout << left[i].x << ' ' << left[i].y << ' ' << right[i].x << ' ' << right[i].y << '\n';
    }*/
    for (int i = 1; i < n; ++i) {
        if (left[i+1].x == right[i].x || left[i+1].y == right[i].y) {
            cout << i;
            return 0;
        }
    }
    cout << -1;

    return 0;
}

-1

2009_phamduc 10:32 p.m. 11 Tháng 10, 2023

??????

-4

PhanHuyKhang 10:42 a.m. 21 Tháng 2, 2021 ← đã chỉnh sửa →

easy mà

1 phản hồi

6

20tiltvthaison 2:44 p.m. 11 Tháng 2, 2021

Test 1 bị sai ( n = 6 mà dãy a có 7 phần tử )

1 phản hồi

-1

Lê_Gia_Khánh 11:34 p.m. 19 Tháng 12, 2020 ← đã chỉnh sửa →

bài này được phết :))