Kortit I

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
    {
        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 = match initial_method(t.num_cards, t.p1_points, t.p2_points) {
            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);
    }
}

Test 1

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 2

Group: 2, 3

Verdict: WRONG ANSWER

Test 3

Group: 3

Verdict: WRONG ANSWER

Test 4

Group: 3

Verdict: WRONG ANSWER

Test 5

Group: 3

Verdict: WRONG ANSWER

Test 6

Group: 3

Verdict: WRONG ANSWER

Test 7

Group: 3

Verdict: WRONG ANSWER

Test 8

Group: 3

Verdict: WRONG ANSWER

Test 9

Group: 3

Verdict: WRONG ANSWER

Test 10

Group: 3

Verdict: WRONG ANSWER

Test 11

Group: 3

Verdict: WRONG ANSWER

Test 12

Group: 3

Verdict: WRONG ANSWER

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 3

Verdict: WRONG ANSWER

Test 15

Group: 3

Verdict: WRONG ANSWER

Test 16

Group: 3

Verdict: WRONG ANSWER

Test 17

Group: 3

Verdict: WRONG ANSWER

Test 18

Group: 3

Verdict: WRONG ANSWER

Test 19

Group: 3

Verdict: WRONG ANSWER

Test 20

Group: 3

Verdict: WRONG ANSWER