โจทย์: อาร์เรย์ A ค่าอยู่ในช่วง -1 ถึง 1 มีคิวรี่ m คู่ Q[i]=(li,ri) ตอบ 1 หากจัดเรียง A ใหม่ได้ว่าผลรวมช่วง li ถึง ri = 0 มิฉะนั้น 0
Input: A=[-1,1,1,1,-1], Q=[[1,1],[2,3],[3,5],[2,5],[1,5]] → Output: [0,1,0,1,0]
ขั้นตอนแก้
z := count of negative values in A
if z > n-z: z := n-z
for each query (l,r):
len := r - l + 1
if (len % 2 == 0) and (len/2 <= z): print 1 else 0ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A, vector<vector<int>> Q) {
int n = A.size(), m = Q.size(), z = 0;
for (int a, i = 0; i < n; ++i) z += a < 0;
if (z > n - z) z = n - z;
for (int i = 0; i < m; i++) {
int l = Q[i][0], r = Q[i][1];
cout << (((r - l) % 2 && (r - l + 1) / 2) <= z) << ", ";
}
}
int main() {
vector<int> A = {-1,1,1,1,-1};
vector<vector<int>> Q = {{1,1},{2,3},{3,5},{2,5},{1,5}};
solve(A,Q);
}Input
{-1,1,1,1,-1}, {{1,1},{2,3},{3,5},{2,5},{1,5}}Output
1, 0, 1, 0, 1,
