Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### putong's blog

By putong, history, 10 days ago, The problem : 1605B - Reverse Sort

This problem has $2$ traditions.

Now the $m$ is $0$.

1. This array had not been sorted.

The $m$ is $1$.

Make $k$ is the number of 1s.

if has one $i(0<i<n+1):$

$s_i=1\ and\ i<n-k+1 :$ We need to add $i$ to ans.

$s_i=0\ and\ i>n-k :$ We need to add $i$ to ans, too.

The code is very short:

#include <bits/stdc++.h>
using namespace std;
char s;
int n;
int a;
signed main () {
int t;
cin >> t;
while (t --) {
cin >> n >> s + 1;
int is = 0;
for (int i = 1;i <= n; ++ i) {
if (s[i] == '1') is ++;
}
int cnt = 0;
memset (a, 0, sizeof a);
for (int i = 1;i <= n; ++ i) {
if (s[i] == '1' && i <= n - is) a[++ cnt] = i;
if (s[i] == '0' && i > n - is) a[++ cnt] = i;
}
if (cnt == 0) cout << 0 << endl;
else {
cout << 1 << endl;
cout << cnt << ' ';
for (int i = 1;i <= cnt; ++ i) {
cout << a[i] << ' ';
}
cout << endl;
}
}
return 0;
}


By putong, history, 2 months ago, I think this problem is not very hard and it's interesting.

Description:

You are given $2$ arrays $a$ and $b$ and the length of them is $n$.

• $1$, $3$, $5$, ......, $2 * n - 1$ is in $a$.

• $2$, $4$, $6$, ......, $2 * n$ is in $b$.

$\mathrm{Algorithm}\ 1:$

we use the array $mp_i$ is $i$ the distance to the $a_1$ or $b_1$.

the code is:

for (int i = 1;i <= n; ++ i) cin >> a[i], mp[a[i]] = i - 1;
for (int j = 1;j <= n; ++ j) cin >> b[i], mp[b[i]] = i - 1;


We can enumerate the $i$ and the $j$, and the answer is $mp_{a_i}\ +\ mp_{b_j}$.

the code:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <iomanip>
#include <cctype>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <deque>
#include <ctime>
#include <sstream>
#include <list>
#include <bitset>
#include <climits>
#include <functional>
#include <complex>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int int
#define itn int
using namespace std;
using namespace __gnu_pbds;
typedef long long ll ;
typedef pair <int, int> PII;
#define x first
#define y second
#define pq priority_queue
const double pi = acos (-1);
namespace fastIO {
template <class T>
inline void read (T &x) {
x = 0;
bool fu = 0;
char ch = 0;
while (ch > '9' || ch < '0') {
ch = getchar ();
if (ch == '-') fu = 1;
}
while (ch <= '9' && ch >= '0') x = (x * 10 - 48 + ch), ch = getchar ();
if (fu) x = -x;
}
int x = 0;
bool fu = 0;
char ch = 0;
while (ch > '9' || ch < '0') {
ch = getchar ();
if (ch == '-') fu = 1;
}
while (ch <= '9' && ch >= '0') x = (x * 10 - 48 + ch), ch = getchar ();
return fu ? -x : x;
}
template <class T, class... Args>
inline void read (T& t, Args&... args) {
}
char num;
template <class T>
inline void write (T x) {
if (x == 0) {
putchar ('0');
return ;
}
T tmp = x > 0 ? x : -x;
if (x < 0) putchar ('-');
register int ct = 0;
while (tmp) {
num[ct ++] = tmp % 10 + '0';
tmp /= 10;
}
while (ct) {
putchar (num[-- ct]);
}
}
template <class T>
inline void write (T x, char ch) {
write (x);
putchar (ch);
}
}
using namespace fastIO;
int a, b;
int mp;
int mini;
int c;
signed main () {
int t;
cin >> t;
while (t --) {
memset (mp, 0, sizeof mp);
memset (mini, 0, sizeof mini);
int n;
int ans = 0x7f7f7f7f;
for (int i = 1;i <= n; ++ i) {
mp[a[i]] = i - 1;
}
for (int i = 1;i <= n; ++ i) {
mp[b[i]] = i - 1;
}
if (a < b) {
cout << "0" << endl;
}
else {
for (int i = 1;i <= 2 * n; i += 2) {
for (int j = 1;j <= 2 * n; j += 2) {
if (i < j) ans = min (ans, mp[i] + mp[j]);
}
}
cout << ans << endl;
}
}
return 0;
}


time: $O(tn^2)$.

$\mathrm{Algorithm}\ 2:$

we can use $mini_i\ =\ \mathrm{min}_{i=\frac{i}{2}}^{n}mp_{2i}$.

and the time is $O(tn)$.

code :

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <iomanip>
#include <cctype>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <deque>
#include <ctime>
#include <sstream>
#include <list>
#include <bitset>
#include <climits>
#include <functional>
#include <complex>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int int
#define itn int
using namespace std;
using namespace __gnu_pbds;
typedef long long ll ;
typedef pair <int, int> PII;
#define x first
#define y second
#define pq priority_queue
const double pi = acos (-1);
namespace fastIO {
template <class T>
inline void read (T &x) {
x = 0;
bool fu = 0;
char ch = 0;
while (ch > '9' || ch < '0') {
ch = getchar ();
if (ch == '-') fu = 1;
}
while (ch <= '9' && ch >= '0') x = (x * 10 - 48 + ch), ch = getchar ();
if (fu) x = -x;
}
int x = 0;
bool fu = 0;
char ch = 0;
while (ch > '9' || ch < '0') {
ch = getchar ();
if (ch == '-') fu = 1;
}
while (ch <= '9' && ch >= '0') x = (x * 10 - 48 + ch), ch = getchar ();
return fu ? -x : x;
}
template <class T, class... Args>
inline void read (T& t, Args&... args) {
}
char num;
template <class T>
inline void write (T x) {
if (x == 0) {
putchar ('0');
return ;
}
T tmp = x > 0 ? x : -x;
if (x < 0) putchar ('-');
register int ct = 0;
while (tmp) {
num[ct ++] = tmp % 10 + '0';
tmp /= 10;
}
while (ct) {
putchar (num[-- ct]);
}
}
template <class T>
inline void write (T x, char ch) {
write (x);
putchar (ch);
}
}
using namespace fastIO;
int a, b;
int mp;
int mini;
int c;
signed main () {
int t;
cin >> t;
while (t --) {
memset (mp, 0, sizeof mp);
memset (mini, 0, sizeof mini);
int n;
int ans = 0x7f7f7f7f;
for (int i = 1;i <= n; ++ i) {
mp[a[i]] = i - 1;
}
for (int i = 1;i <= n; ++ i) {
mp[b[i]] = i - 1;
}
mini[2 * n] = mp[2 * n];
for (int i = 2 * n - 2;i >= 2; i -= 2) {
mini[i] = min (mini[i + 2], mp[i]);
}
if (a < b) {
cout << "0" << endl;
}
else {
for (int i = 1;i <= 2 * n; i += 2) {
ans = min (ans, mp[i] + mini[i + 1]);
}
cout << ans << endl;
}
}
return 0;
}