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

Codeforces Round #743 (Div.2) B — Swaps
Difference between en7 and en8, changed 2,785 character(s)
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:↵

```cpp↵
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:↵

```cpp↵
#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;↵
}↵
inline int read () {↵
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) {↵
read (t);↵
read (args...);↵
}↵
char num[40];↵
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[100005], b[100005];↵
int mp[200010];↵
int mini[200010];↵
int c[100005];↵
signed main () {↵
int t;↵
cin >> t;↵
while (t --) {↵
memset (mp, 0, sizeof mp);↵
memset (mini, 0, sizeof mini);↵
int n;↵
read (n);↵
int ans = 0x7f7f7f7f;↵
for (int i = 1;i <= n; ++ i) {↵
read (a[i]);↵
mp[a[i]] = i - 1;↵
}↵
for (int i = 1;i <= n; ++ i) {↵
read (b[i]);↵
mp[b[i]] = i - 1;↵
}↵
if (a[1] < b[1]) {↵
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 :↵

```cpp↵
#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;↵
}↵
inline int read () {↵
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) {↵
read (t);↵
read (args...);↵
}↵
char num[40];↵
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[100005], b[100005];↵
int mp[200010];↵
int mini[200010];↵
int c[100005];↵
signed main () {↵
int t;↵
cin >> t;↵
while (t --) {↵
memset (mp, 0, sizeof mp);↵
memset (mini, 0, sizeof mini);↵
int n;↵
read (n);↵
int ans = 0x7f7f7f7f;↵
for (int i = 1;i <= n; ++ i) {↵
read (a[i]);↵
mp[a[i]] = i - 1;↵
}↵
for (int i = 1;i <= n; ++ i) {↵
read (b[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[1] < b[1]) {↵
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;↵
}↵
```

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English putong 2021-09-19 15:21:43 2785
en7 English putong 2021-09-19 15:16:28 2852
en6 English putong 2021-09-19 15:11:49 162
en5 English putong 2021-09-19 15:07:30 14
en4 English putong 2021-09-19 15:06:15 22
en3 English putong 2021-09-19 15:05:46 22
en2 English putong 2021-09-19 15:04:51 79
en1 English putong 2021-09-19 15:04:16 358 Initial revision (published)