Description

Given an initial Spider Solitaire position, Little A wants to know whether it is possible to win. If yes, output $\texttt{YES}$ and the minimum number of moves needed to win. Otherwise output $\texttt{NO}$.

Little A also wants to know, for each card $i$, the minimum number of moves needed to move $i$, including the move that moves $i$ itself. If it is impossible to move it, output -1.

“Simplified statement”

There are $m$ horizontal piles of numbers, containing a total of $n$ numbers. Each pile has $0$ or more numbers. Across all piles are exactly all numbers from $1$ to $n$.

You may take some consecutive numbers $a_1,a_2,\cdots,a_c$ on the right end of a pile that are strictly decreasing with common difference $-1$, and move them in the original order to the right end of another non-empty pile, if and only if the rightmost number of that non-empty pile is a number $b=a_1+1$.

Find the minimum number of moves to move all $n$ numbers into a single pile such that they are decreasing from left to right. If there is no solution, output $\texttt{NO}$.

In addition, for each number $i$, you must output the minimum number of moves needed to move $i$.

Input Format

The first line contains an integer $T$, the subtask id.
The second line contains two integers $n,m$, representing the number of cards in the deck and the number of piles.
Then follow $m$ lines. Each line starts with an integer $c$ for the number of cards in that pile, followed by $c$ integers $b_1,b_2,\cdots,b_c$ describing the pile from left to right.

Output Format

If you can win, output $\texttt{YES}$ on the first line and the minimum number of moves on the second line. Otherwise output one line $\texttt{NO}$.

Whether you can win or not, you also need to output $n$ lines. The $i$-th line contains an integer between $-1$ and $n$, indicating the minimum number of moves needed to move $i$.

0
9 3
6 9 8 4 3 2 1
2 7 5
1 6

YES
4
1
1
1
1
1
2
3
-1
-1

0
13 4
4 13 10 1 7
3 11 4 8
4 6 5 3 2
2 12 9

YES
10
2
2
2
3
3
3
1
1
3
6
7
8
-1

0
5 1
5 5 4 3 2 1

YES
0
-1
-1
-1
-1
-1

0
17 10
2 12 14
1 3
3 1 13 15
0
2 9 8
1 5
3 16 7 6
2 11 2
1 4
2 17 10

YES
14
4
1
1
1
1
1
1
1
1
2
3
4
3
1
2
4
-1

0
13 4
4 10 1 13 7
4 11 12 4 8
4 6 5 3 2
1 9

NO
-1
2
2
3
3
3
1
1
-1
-1
6
5
-1

Hint

“Sample 1 Explanation”

Since 1,2,3,4,5 can be moved directly, it takes at least 1 move to move them.
Since you need to move 5 to the right of 6 before 6 can be moved, it takes at least 2 moves to move 6.
Since you need to first move 5 to the right of 6, then move 4,3,2,1 to the right of 5 before 7 can be moved, it takes at least 3 moves to move 7.
Clearly, 8,9 cannot be moved.

“Special Judge”

This problem uses Special Judge. Please strictly follow the output format:

• If you correctly output whether you can win, and if you can win, you correctly output the minimum number of moves, you will get at least $40\%$ of the score for this test.
• Based on the previous part, if you correctly output the minimum number of moves for each card, you will get the remaining $60\%$ of the score for this test. That is, if your output is wrong in the previous part, you will not get any score for this part either.
• If your output format is wrong, you will get $0\%$ for this test, including but not limited to only outputting whether you can win.
• Note in particular that if you cannot correctly compute the minimum number of moves for each card, please randomly output any integers in $[-1,n]$, otherwise you will get $0\%$ for this test.
• You must output a newline at the end of every line, including the last line.

The checker is given at the end of the problem.

“Constraints and Notes”

This problem uses bundled testdata.

• Subtask #0 (0 points): the samples.
• Subtask #1 (15 points): $n\leq 3\times 10^3$, $m=2$.
• Subtask #2 (15 points): $b_i>b_{i+1}\ (1\leq i<c)$, $n\leq 3\times 10^3$.
• Subtask #3 (25 points): $n\leq 14$, $m=3$.
• Subtask #4 (30 points): $n\leq 3\times 10^3$.
• Subtask #5 (15 points): no special restrictions.

For $100\%$ of the testdata, $1\leq n,m\leq 5\times 10^4$. Time limit: 1s. Memory limit: 512MB.

“Source”

Sweet Round 07 D.
idea & solution & data: Alex_Wei; validation: chenxia25.

Below is the checker. You need testlib.h to compile successfully.

#include "testlib.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb emplace_back
#define mp make_pair 
#define vint vector <int>
#define vpii vector <pii>
#define all(x) x.begin(),x.end()
#define sor(x) sort(all(x))
#define rev(x) reverse(all(x))
#define mem(x,v) memset(x,v,sizeof(x))

#define rint inf.readInt
#define reof inf.readEof()
#define reoln inf.readEoln()
#define rspace inf.readSpace()

// wrong answer : quitf(_wa,"The answer is wrong")
// accepted :  quitf(_ok,"The answer is correct")
// partly correct : quitp(0.5,"The answer is partly correct")

int main(int argc,char* argv[]){
	registerTestlibCmd(argc,argv);
	
	string jans=ans.readToken();
	string pans=ouf.readToken(jans);
	int sub=rint(),n=rint(),diff=0;
	
	if(jans=="YES"){
		int jstep=ans.readInt();
		int pstep=ouf.readInt();
		if(jstep!=pstep)quitf(_wa,"The answer is wrong");
	}
	
	for(int i=1;i<=n;i++){
		int jans=ans.readInt();
		int pans=ouf.readInt();
		if(jans!=pans)diff=1;
	}
	
	while(!ouf.seekEof())ouf.readToken();
	while(!inf.seekEof())inf.readToken();
	while(!ans.seekEof())ans.readToken();
	if(diff)quitp(0.4,"The answer is partially correct");
	else quitf(_ok,"OK, you AK IOI");
	
	return 0;
}

Translated by ChatGPT 5