Codeforces #182 Div2 A "Eugeny and Array"
問題
http://codeforces.com/contest/302/problem/A
訳
ユージャニー(?)はn個の整数 a_1, a_2, ... a_n という配列aを持っている。
この配列の各要素は -1 か 1 である。
また、m個のクエリがある。
i番目のクエリでは li ri( 1 <= li <= ri <= n ) という整数のペアが与えられる。
応答は、もし配列の要素を好きなように再配置して
a_li + a_li+1 + ... + a_ri = 0とする事が可能であれば、1を出力せよ。
そうでなければ0を出力せよ。
制約
1 <= n, m <= 2 * 10^5
考えた事
liからriの範囲をlenとすると、
lenが偶数でないとダメ
配列全体に1と-1がそれぞれlen / 2個以上ないとダメ
ソースコード
int main() { int N, M; cin >> N >> M; int plus = 0, minus = 0; for( int i = 0; i < N; i++ ){ int t; cin >> t; if( t == 1 ) plus++; if( t == -1 ) minus++; } for( int i = 0; i < M; i++ ){ int l, r; cin >> l >> r; int n = r - l + 1; bool ok = (n % 2 == 0) && (n / 2 <= plus) && (n / 2 <= minus); printf( "%d\n", ok ? 1 : 0 ); } }