There are $n$ double-sided cards with an integer number on each side, laid on a table. Only the top side of each card is visible.
Two players are playing a game with the cards. They take turns to choose a card and flip it, making the visible side hidden and the hidden side visible. One of the players wants the sum of the integers on the visible sides to be even, while the other player wants the sum to be odd. The game lasts for $k$ turns.
Given the parity the first player wants, who would win if both players play optimally?
The first line contains three integers $n$, $k$ and $m$ ($1 \leq n \leq 10^6, 1 \leq k \leq 10^9, 0 \leq m \leq 1$), representing the number of cards, the number of turns, and the parity the first player wants for the sum of the integers on the visible sides, respectively. If $m=0$, the required parity is even, otherwise it's odd.
Each of the following $n$ lines contains two integers $x_i$ and $y_i$ ($1 \leq x_i,y_i \leq 10^9$), where $x_i$ is the number on the visible side of card $i$, and $y_i$ is the number on the hidden side of it.
Print a single line with $1$ if the first player would win. Otherwise, print $2$.
| Input | Output |
|---|---|
5 200 1 1 11 2 4 11 11 33 4 5 5 Copy
|
2 Copy
|
1 5 1 1 1 Copy
|
1 Copy
|
First observation, It doesn't matter what the values on the cards are, it only matters if the value is even or odd.
If we substitute an odd value with $1$ and an even value with $0$, then we can observe that there are only 4 possible combinations:
The combinations $1,1$ and $0,0$ are equivalent, so are $1,0$ and $0,1$
Now we have a couple of cases we need to cover:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());
const int N = 1e6;
int n,m,have[3],par;
long long k;
int main(){
scanf("%d%lld%d",&n,&k,&m);
for(int i = 0,a,b;i < n;i++){
scanf("%d%d",&a,&b);
a&=1;
b&=1;
par^=a;
if(b > a)swap(a,b);
have[b + a] = 1;
}
if(!have[1])return printf("%d\n",m == par ? 1 : 2),0;
if(!have[0] && !have[2])return printf("%d\n",(par^(k&1)) == m ? 1 : 2),0;
printf("%d\n",(k&1) ? 1 : 2);
}