B. Sequence Game | Codeforces Solution | Codeforces Round 894 (Div. 3)
Tema and Vika are playing the following game. First, Vika comes up with a sequence of positive integers 𝑎 of length 𝑚 and writes it down on a piece of paper. Then she takes a new piece of paper and writes down the sequence 𝑏 according to the following rule: First, she writes down 𝑎1 . Then, she writes down only those 𝑎𝑖 (2≤𝑖≤𝑚 ) such that 𝑎𝑖−1≤𝑎𝑖 . Let the length of this sequence be denoted as 𝑛 .
B. Sequence Game
time limit per test: 2 seconds | memory limit per test: 256 megabytes
Tema and Vika are playing the following game.
First, Vika comes up with a sequence of positive integers a of length m and writes it down on a piece of paper. Then she takes a new piece of paper and writes down the sequence b according to the following rule:
- First, she writes down a1.
- Then, she writes down only those ai (2 ≤ i ≤ m) such that ai−1 ≤ ai. Let the length of this sequence be denoted as n.
For example, from the sequence a = [4, 3, 2, 6, 3, 3], Vika will obtain the sequence b = [4, 6, 3].
She then gives the piece of paper with the sequence b to Tema. He, in turn, tries to guess the sequence a.
Tema considers winning in such a game highly unlikely, but still wants to find at least one sequence a that could have been originally chosen by Vika. Help him and output any such sequence.
Note that the length of the sequence you output should not exceed the input sequence length by more than two times.
Input
Each test consists of multiple test cases. The first line of input data contains a single integer t (1 ≤ t ≤ 104) — the number of test cases. This is followed by a description of the test cases.
The first line of each test case contains a single integer n (1 ≤ n ≤ 2⋅105) — the length of the sequence b.
The second line of each test case contains n integers b1, b2, b3, …, bn (1 ≤ bi ≤ 109) — the elements of the sequence.
The sum of the values of n over all test cases does not exceed 2⋅105.
Output
For each test case, output two lines. In the first line, output a single integer m — the length of the sequence (n ≤ m ≤ 2⋅n). In the second line, output m integers a1, a2, a3, …, am (1 ≤ ai ≤ 109) — the assumed sequence that Vika could have written on the first piece of paper.
If there are multiple suitable sequences, you can output any of them.
Example
Input
6 3 4 6 3 3 1 2 3 5 1 7 9 5 7 1 144 2 1 1 5 1 2 2 1 1
Output
6 4 3 2 6 3 3 3 1 2 3 6 1 7 9 3 5 7 1 144 2 1 1 6 1 2 2 1 1 1
Note
The first sample is explained in the problem statement.
In the second sample, Vika could have chosen the original sequence.
void solve()
{
int n;
cin >> n;
vi v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
vi ans;
ans.pb(v[0]);
for (int i = 1; i < n; i++)
{
if (v[i] >= v[i - 1])
ans.pb(v[i]);
else
{
ans.pb(v[i]);
ans.pb(v[i]);
}
}
cout << ans.size() << endl;
print(ans);
}
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define F first
#define S second
#define pb push_back
#define si set<int>
#define vi vector<int>
#define pii pair<int, int>
#define vpi vector<pii>
#define vpp vector<pair<int, pii>>
#define mii map<int, int>
#define mpi map<pii, int>
#define spi set<pii>
#define endl "\n"
#define sz(x) ((int)x.size())
#define all(p) p.begin(), p.end()
#define double long double
#define que_max priority_queue<int>
#define que_min priority_queue<int, vi, greater<int>>
#define bug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define print(a) \
for (auto x : a) \
cout << x << " "; \
cout << endl
#define print1(a) \
for (auto x : a) \
cout << x.F << " " << x.S << endl
#define print2(a, x, y) \
for (int i = x; i < y; i++) \
cout << a[i] << " "; \
cout << endl
#define scanit(a, n) \
for (ll indexaa = 0; indexaa < n; indexaa++) \
cin >> a[indexaa];
inline int power(int a, int b)
{
int x = 1;
while (b)
{
if (b & 1)
x *= a;
a *= a;
b >>= 1;
}
return x;
}
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args)
{
const char *comma = strchr(names + 1, ',');
cout.write(names, comma - names) << " : " << arg1 << " | ";
__f(comma + 1, args...);
}
const int N = 200005;
void solve()
{
int n;
cin >> n;
vi v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
vi ans;
ans.pb(v[0]);
for (int i = 1; i < n; i++)
{
if (v[i] >= v[i - 1])
ans.pb(v[i]);
else
{
ans.pb(v[i]);
ans.pb(v[i]);
}
}
cout << ans.size() << endl;
print(ans);
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
clock_t z = clock();
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
Raunit Verma
Technical Writer at CodingKaro
