pub struct TestInfo {
pub num_cards: usize,
pub p1_points: usize,
pub p2_points: usize,
}
pub fn initial_method(
num_cards: usize,
num_points_p1: usize,
num_points_p2: usize,
) -> Option<(Vec<usize>, Vec<usize>)> {
// 5 4 3 2 1
// 5 -> just reduces the problem to (n - 1)
// anything else -> means that card can not be played against the enemy's such card, meaning a
// tie won't result there, meaning one player will win there, meaning p2 will win there, as
// their going to have a n to place there
// -> Thus it is not possible to have a (n - 1) tie. Instead, an n or (n - 2) tie is the best
// possible, and in the latter case, both players will have to get one point
//
// In fact, all ties, a count k of them, just cause the problem to become (n - k) instead
// (regardless of the place of the ties)
// 5 4 3 2 1 4, 1
// 1 5 4 3 2
//
// 5 4 3 2 1 3, 2
// 1 3 5 4 2
//
// 5 4 3 2 1 1, 4
// 4 3 2 1 5
//
// 5 4 3 2 1
// 4 5 1 3 2
//
// I.e.: neither 1, nor (n - 1), is ALWAYS a valid option
//
// Picking 1 < x < n - 1 as the first card signifies:
// - that card is no more available to be picked for e(x - 1)
// - that card is no more available to be picked for e(x + 1)
//
// 5 4 3 2 1
// 3 5 4 1 2
//
// 5 4 3 2 1
// 2 5 4 3 1
//
// Whenever a card y(a > b) is picked as a response to e(b), it reduces the amount of cards
// y(x >= a) available to win against all cards e(x <= a - 2).
// It does not affact the ability for winning against cards e(x >= a - 2)
// 1
// b
//
// Actually, a better way to represent this would be by saying that:
// Whenever a card y(a > b + 1) is picked as a response to e(b), it makes the card y(b + 1)
// useless. Or, actually, if b > 1 (as would generally be the case), it causes a chain
// reaction, where yes, the card y(b + 1) can be played against cards e(x < b), but now there's
// b + 1 (of which one is the card 1, which can not be used to win, so really, there's only b
// cards that matter in this sense) cards of player Y available to be played against b - 1 cards
// of the enemy. There is a mismatch, and thus one of those cards will inevitable go to waste,
// i.e. be unable to be used to win an exchange, and must thus be used to lose instead.
//
// 5 4 3 2 1
// 1 2 5 4 3
//
// 5 4 3 2 1
// 1 2 4 3 5
//
// And along with the effect mentioned in the previous paragraph, there is also the effect that
// there will now be one card fewer for winning against cards e(x > b), one card less than
// there are those cards of the enemy. Thus the one card y(x > b + 1) that doesn't exist will
// instead be replaced by the wasted card y(x <= b).
//
// Actually, the previous paragraph mentioned in the previous paragraph is entirely incorrect.
//
// When a card y(a > b) is picked to win against a card e(b), the cards e(e) are split into two
// groups: e(x > b) and e(x <= b). The former group doesn't get any smaller as a result of the
// exchange, but the latter does, as e(b) is included in it. If a == b + 1, then the group of
// cards y(c > b + 1) that can be played against the group of cards e(x > b) does not get any
// smaller. But if a > b + 1, the group y(c > b + 1) does get smaller by one card. This means
// that the amount of times it is possible to win against cards e(x > b) is reduced by one.
// The same applies for picking a card y(a < b) against a card e(b), except the relations are
// reversed.
//
// 5 4 3 2 1
// 1 3 2 4 5
//
// 5 4 3 2 1
// 4 3 2 1 5
//
// 5 4 3 2 1
// 3 5 2 1 4
//
// e(b) => y(a < b)
// e(c < a <=> c < b - 1) can be won against with the cards y(d >= a). That group e(c) of cards does
// not get any smaller but the group y(d) does.
//
//
// Formal Approach:
//
// The game can be thought of as a sequence of exchanges. The game will then have a separate,
// distinct state at each such element of the sequence: a state consisting of the set of cards
// e(x) and y(x).
// Since in the first part of the exercise, the particular game doesn't matter as long as
// it ends up with the right score totals, it doesn't matter in which order the cards are
// represented. Thus it would be helpful to use a convention where the exchanges are ordered
// based on cards e(x) in descending order.
// The above inferences can be formulated thusly. At each element of the sequence of
// exchanges, S(n), regardless of how the game has been played by both players up to this
// point, regardless of which elements the sets E(n) and Y(n) hold, the following holds true.
// The set E(n) can be split into two sets, e(a > o(n)) and e(b <= o(n)). In S(n + 1), if such
// a state exists, i.e. n < N, e(a) will be equally large, while e(b) will have decreased in
// size by one, compared to the state S(n), as that set includes the element e(o(n)).
// It is relevant to define one more set, this time for Y(n): y(a > o(n) + 1). This set
// describes the elements of Y(n) that can be played against e(a) to win. If t(n) == o(n) + 1, then
// the set y(a) does not decrease in size, and thus will remain as equal with e(a) as it was in
// the previous state S(n - 1), provided of course, that n > 0. If, on the other hand, t(n) > o(n) + 1,
// then it does belong in the set y(a), and thus the size of that set decreases. This means that one
// fewer card in e(a) can be won against.
// But what is the effect on the possibilities for losing against E(a > n)? The only
// elements E(n) that might possibly be affected by this are e(c > o(n) + 1). Of course the
// size of e(c) remains constant across state boundaries, and the number of elements y(c <=
// o(n) + 1)
//
// The algorithm:
// It would generate the game state, one exchange at a time, starting from the previously
// described order. Before continuing with producing an exchange sequence for the wins and
// losses though, the algorithm would calculate the number of ties and produce the appropriate
// sequence of the appropriate length to describe the tie exchanges. At the end the algorithm
// could then preprend that sequence to the generated one.
// At each exchange, the algorithm would produce such an exchange, that it produced a win
// for p2 if there are still wins needed to be obtained for that player, and otherwise one
// for p1. The exhange would be made such, that it would not lower the maximum amount of points
// each player can still obtain beyond the point total they are to acquire. The algorithm would
// only need to consider the point maximums separately for each player, as there is no link
// between them.
//
// Thus the only problems remaining are:
// - Edge cases at cards n and 1
// - 1 is the only card that can not be used for winning, and thus choosing that card
// for a losing option does not atually reduce My(n)
// - n is the only card that can not be used to lose, and thus choosing that card for a
// winning option does not actually reduce Me(n)
// - How to avoid accidentally causing a tie, as that is illegal now that the ties have already
// been taken care of before?
// - As E(0) == Y(0), and each exchange is either a win or a loss, which means o(n) !=
// t(n), - no nvm: S(1) = (1, 2), S(2) = (2, 1), then S(3) must be (3, 3).
// IMPORTANT: e(m) and e(l) here are for the state at the start of the next exchange, S(n + 1)!
// - How does choosing a winning card affect maximum losing plays left?
// - If t(n) < e(m), then Me(n) decreases
// - If t(n) >= e(m), then Me(n) does not change
// - How does choosing a losing card affect maximum winning playes left?
// - If t(n) > e(l), then My(n) decreases
// - If t(n) <= e(l), then My(n) does not change
//
// So basically, in the above two cases, if the card t(n) could not be used for winning or
// losing in S(n + 1) anyway, then there would naturally be no reduction in My(n + 1) or Me(n
// + 1)
// (Could consider the above 2 by considering every possible state + exchange combination and
// then finding regularities in the effect)
//
// The algoritm proceeds in descending order from e(m) towards e(l). At S(1), there are 2
// options: t(1) = n - 1 (if p1 = n - 1) or t(1) = 1 (if p2 = n - 1). If neither, t(1) can be
// either.
// S(2): If pc2 < p2, then t(2) = n - 1 + 1 = n. Else, t(2) = n - 1 - 1 = n - 2.
// S(3): If pc2 < p2, then t(3) = n - 2 + 1 = n - 1. Except, this card might've been selected
// for S(1) before. In that case, it is not possible anymore to win this. Nvm, if t(1) = n - 1,
// then p1 = n - 1, which means S(2) should be a loss anyway, and the only win should be at
// S(n).
// Thus n - 1 is actually a secure choice here. If instead pc1 < p1, then t(3) = n - 2 - 1
// = n - 3.
//
//
// General rule
//
// The cases of p1 = n - 1 and p2 = n - 1 can be thought of as a special case for which its own logic exists.
// p1 case: t(i) = n - i, for every case i != n. t(n) = n.
// p2 case: t(i) = n - i + 2, for every case i != 1. t(1) = 1.
//
// For every other case, the wins will be generated first, and then the losses. (Apart from
// S(1) of course.) For each win, t(i) = n - i + 2. For each loss, t(i) = n - i.
// E: 7 6 5 4 3 2 1
// Y: 1 7 6 3 2 5 4
// Me: 6 4 3 2 1 0 0 0
// My: 6 6 5 4 3 2 1 0
// Note: The "base" M() reduction comes into play only if that exchange was indeed winnable or
// losable
//
// Note: At S(6) and S(7), the order of the 5 and 4 don't matter.
//
// Walkthrough:
// c = 7, p1 = 3, p2 = 4
// t(1) = 1, as p1 < n - 1 and p2 < n - 1
// t(2) = n - 2 + 2 = n, as pc2 < p2 - 2, the winning logic
// t(3) = n - 3 + 2 = n - 1, as pc2 < p2 - 2, the winning logic
//
// Normally, the winning would continue here, with t(4) = n - 2. But since pc2 = 2, and both S(n -
// 1) and S(n) must be wins, pc2 < p2 - 2 must hold for another win to be generated. Since p2 -
// 2 = 4, and 2 == 2, the algorithm must switch to losses here.
//
// t(4) = n - 4 as pc2 == p2 - 2, the losing logic
// t(5) = n - 5, the losing logic
// The logic switches here. The lost 2 exchanges can be nothing else apart from a win, so the
// last two cards should just be played here in an arbitrary order. The two cards remaining are
// always those that would've been played in the first two exchanges that grant a loss (after
// S(1) of course) to generate a win instead. In this case, 5 and 4.
// t(6) = 5, ending logic
// t(7) = 4, ending logic
//
// p1 = 5, p2 = 4
// 9 8 7 6 5 4 3 2 1
// 1 9 8 5 4 3 2 7 6
// w(n) = l(n - 2)
//
// p1 = 9, p2 = 3
// 12 11 10 9 8 7 6 5 4 3 2 1
// 1 12 9 8 7 6 5 4 3 2 11 10
// Note: S(n) is a guaranteed win, as it can't be a tie, and no card is less than 1. Thus it is
// necessary to compare pc2 to p2 - 1, not just p2.
if num_points_p1 > (num_cards - 1)
|| num_points_p2 > (num_cards - 1)
|| (num_points_p1 + num_points_p2) > num_cards
|| (!(num_points_p1 == 0 && num_points_p2 == 0)
&& (num_points_p1 == 0 || num_points_p2 == 0))
{
return None;
}
let num_ties = num_cards - num_points_p1 - num_points_p2;
let mut p2_cards = Vec::new();
// let mut maximum_p1_points = num_cards - 1;
// let mut maximum_p2_points = num_cards - 1;
let mut current_p1_points = 0;
let mut current_p2_points = 0;
let mut cards = Vec::new();
for i in (1..=num_cards).rev() {
cards.push(i);
}
// means that p2 = c - ties - p1
if num_points_p2 == 1 {
// i = num_ties is still a tie, and i = num_ties + 1 is S(n)
for i in ((num_ties + 2)..=num_cards).rev() {
p2_cards.push(i - 1);
}
p2_cards.push(num_cards);
for i in (1..=num_ties).rev() {
p2_cards.push(i);
}
return Some((cards, p2_cards));
} else {
p2_cards.push(num_ties + 1);
current_p1_points += 1;
}
// This is relevant in the case of c = 3, p1 = 1, p2 = 2
let mut switch_to_losses = 2;
let mut switch_to_losses_happened = false;
for i in ((num_ties + 3)..num_cards).rev() {
if current_p2_points < (num_points_p2 - 2) {
p2_cards.push(i + 1);
current_p2_points += 1;
} else if current_p1_points < num_points_p1 {
if !switch_to_losses_happened {
switch_to_losses = i;
switch_to_losses_happened = true;
}
p2_cards.push(i - 1);
current_p1_points += 1;
} else {
return None;
}
// maximum_p1_points -= 1;
// maximum_p2_points -= 1;
// if maximum_p1_points < (num_points_p1 - current_p1_points) {
// return None;
// }
// if maximum_p2_points < (num_points_p2 - current_p2_points) {
// return None;
// }
}
// There will always be at least two wins for p2, because otherwise the answer is already
// generated before and this logic is never reached. If there are only two wins, they will both happen
// here
p2_cards.push(switch_to_losses + 1);
p2_cards.push(switch_to_losses);
for i in (1..=num_ties).rev() {
p2_cards.push(i);
}
Some((cards, p2_cards))
}
use std::io::stdin;
struct TestInfo {
num_cards: usize,
p1_points: usize,
p2_points: usize,
}
fn main() {
let mut l = String::new();
stdin().read_line(&mut l).unwrap();
let num_tests: usize = l.trim().parse().unwrap();
let mut tests: Vec<TestInfo> = Vec::with_capacity(num_tests);
for _ in 0..num_tests {
let mut tl = String::new();
stdin().read_line(&mut tl).unwrap();
let mut nums = tl.trim().split(' ');
let c: usize = nums.next().unwrap().parse().unwrap();
let p1: usize = nums.next().unwrap().parse().unwrap();
let p2: usize = nums.next().unwrap().parse().unwrap();
tests.push(TestInfo {
num_cards: c,
p1_points: p1,
p2_points: p2,
});
}
for i in 0..num_tests {
let t = &tests[i];
let answer_tmp = initial_method(t.num_cards, t.p1_points, t.p2_points);
let answer = match answer_tmp {
None => {
println!("NO");
continue;
}
Some(a) => {
println!("YES");
a
}
};
let p1_cards = answer
.0
.into_iter()
.map(|c| c.to_string())
.collect::<Vec<String>>()
.join(" ");
let p2_cards = answer
.1
.into_iter()
.map(|c| c.to_string())
.collect::<Vec<String>>()
.join(" ");
println!("{}", p1_cards);
println!("{}", p2_cards);
}
}
