結果
| 問題 | No.1698 Face to Face |
| ユーザー |
 LayCurse
|
| 提出日時 | 2021-09-12 19:46:09 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 28,962 bytes |
| コンパイル時間 | 3,961 ms |
| コンパイル使用メモリ | 258,616 KB |
| 実行使用メモリ | 38,796 KB |
| 最終ジャッジ日時 | 2024-07-19 09:53:21 |
| 合計ジャッジ時間 | 18,126 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | WA | - |
| testcase_04 | AC | 643 ms
29,952 KB |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | AC | 184 ms
27,392 KB |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | AC | 2 ms
5,376 KB |
| testcase_14 | AC | 2 ms
5,376 KB |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | AC | 2 ms
5,376 KB |
| testcase_36 | AC | 2 ms
5,376 KB |
| testcase_37 | AC | 2 ms
5,376 KB |
| testcase_38 | AC | 2 ms
5,376 KB |
| testcase_39 | AC | 2 ms
5,376 KB |
| testcase_40 | AC | 3 ms
5,376 KB |
| testcase_41 | AC | 2 ms
5,376 KB |
| testcase_42 | AC | 2 ms
5,376 KB |
| testcase_43 | AC | 2 ms
5,376 KB |
| testcase_44 | AC | 2 ms
5,376 KB |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
ソースコード
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
template<class T> struct cLtraits_identity{
using type = T;
}
;
template<class T> using cLtraits_try_make_signed =
typename conditional<
is_integral<T>::value,
make_signed<T>,
cLtraits_identity<T>
>::type;
template <class S, class T> struct cLtraits_common_type{
using tS = typename cLtraits_try_make_signed<S>::type;
using tT = typename cLtraits_try_make_signed<T>::type;
using type = typename common_type<tS,tT>::type;
}
;
void*wmem;
char memarr[96000000];
template<class S, class T> inline auto min_L(S a, T b)
-> typename cLtraits_common_type<S,T>::type{
return (typename cLtraits_common_type<S,T>::type) a <= (typename cLtraits_common_type<S,T>::type) b ? a : b;
}
template<class S, class T> inline auto max_L(S a, T b)
-> typename cLtraits_common_type<S,T>::type{
return (typename cLtraits_common_type<S,T>::type) a >= (typename cLtraits_common_type<S,T>::type) b ? a : b;
}
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
(*arr)=(T*)(*mem);
(*mem)=((*arr)+x);
}
template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
walloc1d(arr, x2-x1, mem);
(*arr) -= x1;
}
template<class T1> void sortA_L(int N, T1 a[], void *mem = wmem){
sort(a, a+N);
}
struct Rand{
unsigned x;
unsigned y;
unsigned z;
unsigned w;
Rand(void){
x=123456789;
y=362436069;
z=521288629;
w=(unsigned)time(NULL);
}
Rand(unsigned seed){
x=123456789;
y=362436069;
z=521288629;
w=seed;
}
inline unsigned get(void){
unsigned t;
t = (x^(x<<11));
x=y;
y=z;
z=w;
w = (w^(w>>19))^(t^(t>>8));
return w;
}
inline double getUni(void){
return get()/4294967296.0;
}
inline int get(int a){
return (int)(a*getUni());
}
inline int get(int a, int b){
return a+(int)((b-a+1)*getUni());
}
inline long long get(long long a){
return(long long)(a*getUni());
}
inline long long get(long long a, long long b){
return a+(long long)((b-a+1)*getUni());
}
inline double get(double a, double b){
return a+(b-a)*getUni();
}
inline int getExp(int a){
return(int)(exp(getUni()*log(a+1.0))-1.0);
}
inline int getExp(int a, int b){
return a+(int)(exp(getUni()*log((b-a+1)+1.0))-1.0);
}
}
;
inline int my_getchar_unlocked(){
static char buf[1048576];
static int s = 1048576;
static int e = 1048576;
if(s == e && e == 1048576){
e = fread_unlocked(buf, 1, 1048576, stdin);
s = 0;
}
if(s == e){
return EOF;
}
return buf[s++];
}
inline void my_putchar_unlocked(const int k){
putchar_unlocked(k);
}
inline void wt_L(char a){
my_putchar_unlocked(a);
}
inline void wt_L(int x){
int s=0;
int m=0;
char f[10];
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
my_putchar_unlocked('-');
}
while(s--){
my_putchar_unlocked(f[s]+'0');
}
}
inline void wt_L(const char c[]){
int i=0;
for(i=0;c[i]!='\0';i++){
my_putchar_unlocked(c[i]);
}
}
template<class S, class T> inline S chmin(S &a, T b){
if(a>b){
a=b;
}
return a;
}
template<class S, class T> inline S chmax(S &a, T b){
if(a<b){
a=b;
}
return a;
}
struct unionFind{
int*d;
int N;
int M;
inline void malloc(const int n){
d = (int*)std::malloc(n*sizeof(int));
M = n;
}
inline void malloc(const int n, const int fg){
d = (int*)std::malloc(n*sizeof(int));
M = n;
if(fg){
init(n);
}
}
inline void free(void){
std::free(d);
}
inline void walloc(const int n, void **mem=&wmem){
walloc1d(&d, n, mem);
M = n;
}
inline void walloc(const int n, const int fg, void **mem=&wmem){
walloc1d(&d, n, mem);
M = n;
if(fg){
init(n);
}
}
inline void init(const int n){
int i;
N = n;
for(i=(0);i<(n);i++){
d[i] = -1;
}
}
inline void init(void){
init(M);
}
inline int get(int a){
int t = a;
int k;
while(d[t]>=0){
t=d[t];
}
while(d[a]>=0){
k=d[a];
d[a]=t;
a=k;
}
return a;
}
inline int connect(int a, int b){
if(d[a]>=0){
a=get(a);
}
if(d[b]>=0){
b=get(b);
}
if(a==b){
return 0;
}
if(d[a] < d[b]){
d[a] += d[b];
d[b] = a;
}
else{
d[b] += d[a];
d[a] = b;
}
return 1;
}
inline int operator()(int a){
return get(a);
}
inline int operator()(int a, int b){
return connect(a,b);
}
inline int& operator[](const int a){
return d[a];
}
inline int size(int a){
a = get(a);
return -d[a];
}
inline int sizeList(int res[]){
int i;
int sz=0;
for(i=(0);i<(N);i++){
if(d[i]<0){
res[sz++] = -d[i];
}
}
return sz;
}
inline int comp(int res[], void *mem = wmem){
int i;
int sz=0;
int*cnt;
walloc1d(&cnt, N, &mem);
for(i=(0);i<(N);i++){
cnt[i] = 0;
}
for(i=(0);i<(N);i++){
cnt[get(i)] = 1;
}
for(i=(0);i<(N);i++){
if(cnt[i]){
cnt[i] = sz++;
}
}
for(i=(0);i<(N);i++){
res[i] = cnt[get(i)];
}
return sz;
}
}
;
long long cReader_ll(long long mn, long long mx, char nx){
int i;
int fg = 0;
int m = 1;
int f = -1;
long long res = 0;
double tmp = 0;
for(;;){
i = my_getchar_unlocked();
if(fg==0 && i=='-'){
fg++;
m = -1;
}
else if('0' <= i && i <= '9'){
fg++;
if(f == -1){
f = i - '0';
}
res = 10 * res + i - '0';
tmp = 10 * tmp + i - '0';
assert(tmp < 1e20);
}
else{
break;
}
}
assert(tmp / 2 <= res);
assert((m==1 && fg >= 1) || (m==-1 && fg >= 2));
assert(mn <= m * res && m * res <= mx);
assert(!(res == 0 && m == -1));
assert(!(res != 0 && f == 0));
assert(!(res == 0 && fg >= 2));
assert(i == nx);
return m * res;
}
void cReader_eof(){
int i;
i = my_getchar_unlocked();
assert(i == EOF);
}
int N;
int A[100000];
int B[100000];
int Z[100000];
unionFind uf;
unionFind uf1;
unionFind uf2;
vector<int> oobaka(){
int i;
int j;
int k;
set<vector<int>> a;
set<vector<int>> b;
vector<int> res;
int mx;
int tmp;
for(k=(0);k<(N);k++){
vector<int> v;
queue<vector<int>> q;
a.clear();
b.clear();
mx = 0;
v.clear();
for(i=(0);i<(N);i++){
v.push_back(A[i]);
}
while(q.size()){
q.pop();
}
q.push(v);
a.insert(v);
while(q.size()){
v = q.front();
q.pop();
for(i=(1);i<(N);i++){
if(v[i-1] <= k && v[i] <= k){
swap(v[i-1], v[i]);
if(a.count(v)==0){
q.push(v);
a.insert(v);
}
swap(v[i-1], v[i]);
}
}
}
v.clear();
for(i=(0);i<(N);i++){
v.push_back(B[i]);
}
while(q.size()){
q.pop();
}
q.push(v);
b.insert(v);
while(q.size()){
v = q.front();
q.pop();
for(i=(1);i<(N);i++){
if(v[i-1] <= k && v[i] <= k){
swap(v[i-1], v[i]);
if(b.count(v)==0){
q.push(v);
b.insert(v);
}
swap(v[i-1], v[i]);
}
}
}
for(auto aa : a){
for(auto bb : b){
int x;
int tmp = 0;
for(x=(0);x<(N);x++){
for(i=(0);i<(N);i++){
if(aa[i]==x){
break;
}
}
for(j=(0);j<(N);j++){
if(bb[j]==Z[x]){
break;
}
}
if(i==j){
tmp++;
}
}
chmax(mx, tmp);
}
}
res.push_back(mx);
}
return res;
}
vector<int> baka(){
int i;
int j;
int k;
vector<int> res;
for(k=(0);k<(N);k++){
int m;
uf1.init(N);
uf2.init(N);
int use[N] = {};
int tmp = 0;
for(i=(1);i<(N);i++){
if(A[i-1] <= k && A[i] <= k){
uf1(i-1, i);
}
}
for(i=(1);i<(N);i++){
if(B[i-1] <= k && B[i] <= k){
uf2(i-1, i);
}
}
for(m=(0);m<(N);m++){
int x;
for(i=(0);i<(N);i++){
if(A[i] == m){
break;
}
}
for(j=(0);j<(N);j++){
if(B[j] == Z[m]){
break;
}
}
for(x=(0);x<(N);x++){
if(!use[x] && uf1(i) == uf1(x) && uf2(j) == uf2(x)){
tmp++;
use[x] = 1;
break;
}
}
}
res.push_back(tmp);
}
return res;
}
struct RBMM{
int mn;
int mx;
}
;
struct RBV{
int mn;
int mx;
int v;
}
;
RBMM rollbackUnionFind_md_func(RBMM a, RBMM b){
return {min_L(a.mn, b.mn),max_L(a.mx, b.mx)};
}
RBV rollbackUnionFind_md_func(RBV a, RBV b){
return {min_L(a.mn, b.mn),max_L(a.mx, b.mx), a.v + b.v};
}
template<class T> struct rollbackUnionFind_md{
int*d;
int N;
int M;
int*h1;
int*h2;
int sz;
int snapsz;
T*v;
T*h3;
inline void malloc(const int n){
d = (int*)std::malloc(n*sizeof(int));
h1 = (int*)std::malloc(2*n*sizeof(int));
h2 = (int*)std::malloc(2*n*sizeof(int));
v = (T*)std::malloc(n*sizeof(T));
h3 = (T*)std::malloc(2*n*sizeof(T));
M = n;
}
inline void malloc(const int n, const int fg){
d = (int*)std::malloc(n*sizeof(int));
h1 = (int*)std::malloc(2*n*sizeof(int));
h2 = (int*)std::malloc(2*n*sizeof(int));
v = (T*)std::malloc(n*sizeof(T));
h3 = (T*)std::malloc(2*n*sizeof(T));
M = n;
if(fg){
init(n);
}
}
inline void free(void){
std::free(d);
std::free(h1);
std::free(h2);
std::free(v);
std::free(h3);
}
inline void walloc(const int n, void **mem=&wmem){
walloc1d(&d, n, mem);
walloc1d(&h1, 2*n, mem);
walloc1d(&h2, 2*n, mem);
walloc1d(&v, n, mem);
walloc1d(&h3, 2*n, mem);
M = n;
}
inline void walloc(const int n, const int fg, void **mem=&wmem){
walloc1d(&d, n, mem);
walloc1d(&h1, 2*n, mem);
walloc1d(&h2, 2*n, mem);
walloc1d(&v, n, mem);
walloc1d(&h3, 2*n, mem);
M = n;
if(fg){
init(n);
}
}
inline void init(const int n){
int i;
N = n;
for(i=(0);i<(n);i++){
d[i] = -1;
}
sz = 0;
snapsz = 0;
}
inline void init(void){
init(M);
}
inline int get(int a){
while(d[a]>=0){
a=d[a];
}
return a;
}
inline int connect(int a, int b){
if(d[a]>=0){
a=get(a);
}
if(d[b]>=0){
b=get(b);
}
if(a==b){
return 0;
}
h1[sz] = a;
h2[sz] = d[a];
h3[sz] = v[a];
sz++;
h1[sz] = b;
h2[sz] = d[b];
h3[sz] = v[b];
sz++;
if(d[a] < d[b]){
d[a] += d[b];
d[b] = a;
v[a] = rollbackUnionFind_md_func(v[a], v[b]);
}
else{
d[b] += d[a];
d[a] = b;
v[b] = rollbackUnionFind_md_func(v[a], v[b]);
}
return 1;
}
inline int operator()(int a){
return get(a);
}
inline int operator()(int a, int b){
return connect(a,b);
}
inline int& operator[](const int a){
return d[a];
}
inline int size(int a){
a = get(a);
return -d[a];
}
inline int sizeList(int res[]){
int i;
int sz=0;
for(i=(0);i<(N);i++){
if(d[i]<0){
res[sz++] = -d[i];
}
}
return sz;
}
inline int undo(void){
if(sz==0){
return 0;
}
sz--;
d[h1[sz]] = h2[sz];
v[h1[sz]] = h3[sz];
sz--;
d[h1[sz]] = h2[sz];
v[h1[sz]] = h3[sz];
if(snapsz > sz){
snapsz = sz;
}
return 1;
}
inline void snapshot(void){
snapsz = sz;
}
inline void rollback(void){
while(snapsz < sz){
sz--;
d[h1[sz]] = h2[sz];
v[h1[sz]] = h3[sz];
sz--;
d[h1[sz]] = h2[sz];
v[h1[sz]] = h3[sz];
}
}
inline T getVal(int a){
a = get(a);
return v[a];
}
inline void setVal(int a, T val){
a = get(a);
v[a] = val;
}
}
;
rollbackUnionFind_md<RBMM> ruf1;
rollbackUnionFind_md<RBMM> ruf2;
rollbackUnionFind_md<RBV> ruf;
int invA[100000];
int invB[100000];
int ftm[100000];
int plc[100000];
int ind[100000];
int liss[20][100000];
set<int> unused;
int solve_uf_doit_sub(int i, int j){
int res = 0;
RBV v;
if(ruf(i) != ruf(j)){
v = ruf.getVal(i);
res -=min_L(v.v, v.mx - v.mn + 1);
v = ruf.getVal(j);
res -=min_L(v.v, v.mx - v.mn + 1);
ruf(i,j);
v = ruf.getVal(i);
res +=min_L(v.v, v.mx - v.mn + 1);
}
return res;
}
int solve_uf_doit(int i){
int x;
int res = 0;
RBV v;
x = invA[i];
if(x-1 >= 0 && A[x-1] <= i){
ruf1(x-1,x);
if(ruf2(x-1) == ruf2(x)){
res += solve_uf_doit_sub(x-1, x);
}
}
if(x+1 < N && A[x+1] <= i){
ruf1(x,x+1);
if(ruf2(x) == ruf2(x+1)){
res += solve_uf_doit_sub(x, x+1);
}
}
x = invB[i];
if(x-1 >= 0 && B[x-1] <= i){
ruf2(x-1,x);
if(ruf1(x-1) == ruf1(x)){
res += solve_uf_doit_sub(x-1, x);
}
}
if(x+1 < N && B[x+1] <= i){
ruf2(x,x+1);
if(ruf1(x) == ruf1(x+1)){
res += solve_uf_doit_sub(x, x+1);
}
}
return res;
}
void solve_uf_doit2(int i){
int x;
x = invA[i];
if(x-1 >= 0 && A[x-1] <= i){
ruf1(x-1,x);
}
if(x+1 < N && A[x+1] <= i){
ruf1(x,x+1);
}
x = invB[i];
if(x-1 >= 0 && B[x-1] <= i){
ruf2(x-1,x);
}
if(x+1 < N && B[x+1] <= i){
ruf2(x,x+1);
}
}
void solve_sub(int s, int e, int sz, int *lis, int dep){
int i;
int j;
int k;
int m;
int sz1;
int sz2;
int x;
int y;
set<int>::iterator it;
if(sz == 0){
for(i=(s);i<(e);i++){
solve_uf_doit2(i);
}
return;
}
if(e-s==1){
solve_uf_doit2(s);
for(i=(0);i<(sz);i++){
x =max_L(ruf1.getVal(invA[lis[i]]).mn, ruf2.getVal(invB[Z[lis[i]]]).mn);
y =min_L(ruf1.getVal(invA[lis[i]]).mx, ruf2.getVal(invB[Z[lis[i]]]).mx);
it = unused.lower_bound(x);
if(it == unused.end() || *it > y){
continue;
}
ftm[lis[i]] = s;
unused.erase(it);
}
return;
}
m = (s + e) / 2;
for(i=(s);i<(m);i++){
solve_uf_doit2(i);
}
sz1 = sz2 = 0;
for(i=(0);i<(sz);i++){
x =max_L(ruf1.getVal(invA[lis[i]]).mn, ruf2.getVal(invB[Z[lis[i]]]).mn);
y =min_L(ruf1.getVal(invA[lis[i]]).mx, ruf2.getVal(invB[Z[lis[i]]]).mx);
it = unused.lower_bound(x);
if(x > y){
continue;
}
if(it == unused.end() || *it > y){
continue;
}
liss[dep+1][sz1++] = lis[i];
}
if(sz1){
ruf1.rollback();
ruf2.rollback();
ruf.rollback();
chmin(sz1, 10 * (m - s));
solve_sub(s,m,sz1,liss[dep+1],dep+1);
}
for(i=(0);i<(sz);i++){
if(ftm[lis[i]] == -1){
lis[sz2++] = lis[i];
}
}
ruf1.snapshot();
ruf2.snapshot();
ruf.snapshot();
solve_sub(m,e,sz2,lis,dep+1);
for(i=(m);i<(e);i++){
solve_uf_doit2(i);
}
}
vector<int> solve(){
int i;
int j;
int k;
vector<int> res(N);
RBV v;
int resval;
ruf1.init(N);
ruf2.init(N);
ruf.init(N);
for(i=(0);i<(N);i++){
ruf1.setVal(i, {i,i});
}
for(i=(0);i<(N);i++){
ruf2.setVal(i, {i,i});
}
for(i=(0);i<(N);i++){
ruf.setVal(i, {i,i,0});
}
for(i=(0);i<(N);i++){
invA[A[i]] = i;
}
for(i=(0);i<(N);i++){
invB[B[i]] = i;
}
for(i=(0);i<(N);i++){
liss[0][i] = i;
}
for(i=(0);i<(N);i++){
ftm[i] = -1;
}
for(i=(0);i<(N);i++){
unused.insert(i);
}
solve_sub(0, N, N, liss[0], 0);
for(i=(0);i<(N);i++){
ind[i] = i;
}
sortA_L(N,ftm);
k = 0;
resval = 0;
for(i=(0);i<(N);i++){
resval += solve_uf_doit(i);
while(k < N && ftm[k] == i){
resval++;
k++;
}
res[i] = resval;
}
return res;
}
int cnt[100000];
int main(){
int i;
wmem = memarr;
Rand rnd;
uf.walloc(100000);
uf1.walloc(100000);
uf2.walloc(100000);
ruf1.walloc(100000);
ruf2.walloc(100000);
ruf.walloc(100000);
N = cReader_ll(2, 100000, '\n');
for(i=(0);i<(N);i++){
A[i] = cReader_ll(1, N, i==N-1?'\n':' ') - 1;
}
for(i=(0);i<(N);i++){
B[i] = cReader_ll(1, N, i==N-1?'\n':' ') - 1;
}
for(i=(0);i<(N);i++){
Z[i] = cReader_ll(1, N, i==N-1?'\n':' ') - 1;
}
for(i=(0);i<(N);i++){
cnt[i] = 0;
}
for(i=(0);i<(N);i++){
cnt[A[i]]++;
}
for(i=(0);i<(N);i++){
assert(cnt[i]==1);
}
for(i=(0);i<(N);i++){
cnt[i] = 0;
}
for(i=(0);i<(N);i++){
cnt[B[i]]++;
}
for(i=(0);i<(N);i++){
assert(cnt[i]==1);
}
for(i=(0);i<(N);i++){
cnt[i] = 0;
}
for(i=(0);i<(N);i++){
cnt[Z[i]]++;
}
for(i=(0);i<(N);i++){
assert(cnt[i]==1);
}
cReader_eof();
vector<int> res;
res = solve();
{
int x7rJoZt9;
for(x7rJoZt9=(0);x7rJoZt9<(N);x7rJoZt9++){
wt_L(res[x7rJoZt9]);
wt_L('\n');
}
}
return 0;
puts("");
for(;;){
vector<int> r1;
vector<int> r2;
vector<int> r3;
N = rnd.get(2,6);
for(i=(0);i<(N);i++){
A[i] = B[i] = Z[i] = i;
}
random_shuffle(A,A+N);
random_shuffle(B,B+N);
random_shuffle(Z,Z+N);
wt_L(N);
wt_L(' ');
wt_L(":");
wt_L(' ');
{
int MsHTBJEM;
for(MsHTBJEM=(0);MsHTBJEM<(N);MsHTBJEM++){
wt_L(A[MsHTBJEM]);
wt_L(' ');
}
}
wt_L(":");
wt_L(' ');
{
int dd01qmIa;
for(dd01qmIa=(0);dd01qmIa<(N);dd01qmIa++){
wt_L(B[dd01qmIa]);
wt_L(' ');
}
}
wt_L(":");
wt_L(' ');
{
int Zs_a1Ftk;
if(N==0){
wt_L('\n');
}
else{
for(Zs_a1Ftk=(0);Zs_a1Ftk<(N-1);Zs_a1Ftk++){
wt_L(Z[Zs_a1Ftk]);
wt_L(' ');
}
wt_L(Z[Zs_a1Ftk]);
wt_L('\n');
}
}
r1 = oobaka();
r2 = baka();
r3 = solve();
{
int B8qxtQZy;
if(N==0){
wt_L('\n');
}
else{
for(B8qxtQZy=(0);B8qxtQZy<(N-1);B8qxtQZy++){
wt_L(r1[B8qxtQZy]);
wt_L(' ');
}
wt_L(r1[B8qxtQZy]);
wt_L('\n');
}
}
{
int pRrsnthG;
if(N==0){
wt_L('\n');
}
else{
for(pRrsnthG=(0);pRrsnthG<(N-1);pRrsnthG++){
wt_L(r2[pRrsnthG]);
wt_L(' ');
}
wt_L(r2[pRrsnthG]);
wt_L('\n');
}
}
{
int Vdr_4aft;
if(N==0){
wt_L('\n');
}
else{
for(Vdr_4aft=(0);Vdr_4aft<(N-1);Vdr_4aft++){
wt_L(r3[Vdr_4aft]);
wt_L(' ');
}
wt_L(r3[Vdr_4aft]);
wt_L('\n');
}
}
assert(r1==r2);
assert(r2==r3);
}
return 0;
}
// cLay version 20210904-1
// --- original code ---
// int N, A[1d5], B[], Z[];
// unionFind uf, uf1, uf2;
//
// VI oobaka(){
// int i, j, k;
// set<VI> a, b;
// VI res;
// int mx, tmp;
// rep(k,N){
// VI v;
// queue<VI> q;
// a.clear();
// b.clear();
//
// mx = 0;
//
// v.clear();
// rep(i,N) v.push_back(A[i]);
// while(q.size()) q.pop();
// q.push(v);
// a.insert(v);
// while(q.size()){
// v = q.front();
// q.pop();
// rep(i,1,N) if(v[i-1] <= k && v[i] <= k){
// swap(v[i-1], v[i]);
// if(a.count(v)==0) q.push(v), a.insert(v);
// swap(v[i-1], v[i]);
// }
// }
//
// v.clear();
// rep(i,N) v.push_back(B[i]);
// while(q.size()) q.pop();
// q.push(v);
// b.insert(v);
// while(q.size()){
// v = q.front();
// q.pop();
// rep(i,1,N) if(v[i-1] <= k && v[i] <= k){
// swap(v[i-1], v[i]);
// if(b.count(v)==0) q.push(v), b.insert(v);
// swap(v[i-1], v[i]);
// }
// }
//
// for(auto aa : a) for(auto bb : b){
// int tmp = 0;
// rep(x,N){
// rep(i,N) if(aa[i]==x) break;
// rep(j,N) if(bb[j]==Z[x]) break;
// if(i==j) tmp++;
// }
// mx >?= tmp;
// }
//
// res.push_back(mx);
// }
// return res;
// }
//
// VI baka(){
// int i, j, k;
// VI res;
// rep(k,N){
// uf1.init(N);
// uf2.init(N);
// int use[N] = {}, tmp = 0;
//
// rep(i,1,N) if(A[i-1] <= k && A[i] <= k) uf1(i-1, i);
// rep(i,1,N) if(B[i-1] <= k && B[i] <= k) uf2(i-1, i);
//
// rep(m,N){
// rep(i,N) if(A[i] == m) break;
// rep(j,N) if(B[j] == Z[m]) break;
// rep(x,N) if(!use[x] && uf1(i) == uf1(x) && uf2(j) == uf2(x)){
// tmp++;
// use[x] = 1;
// break;
// }
// }
//
// res.push_back(tmp);
// }
// return res;
// }
//
//
//
//
// struct RBMM {int mn, mx;};
// struct RBV {int mn, mx, v;};
//
// RBMM rollbackUnionFind_md_func(RBMM a, RBMM b){
// return {min(a.mn, b.mn), max(a.mx, b.mx)};
// }
//
// RBV rollbackUnionFind_md_func(RBV a, RBV b){
// return {min(a.mn, b.mn), max(a.mx, b.mx), a.v + b.v};
// }
//
// template<class T>
// struct rollbackUnionFind_md{
// int *d, N, M;
// int *h1, *h2, sz, snapsz;
// T *v, *h3;
// inline void malloc(const int n){
// d = (int*)std::malloc(n*sizeof(int));
// h1 = (int*)std::malloc(2*n*sizeof(int));
// h2 = (int*)std::malloc(2*n*sizeof(int));
// v = (T*)std::malloc(n*sizeof(T));
// h3 = (T*)std::malloc(2*n*sizeof(T));
// M = n;
// }
// inline void malloc(const int n, const int fg){
// d = (int*)std::malloc(n*sizeof(int));
// h1 = (int*)std::malloc(2*n*sizeof(int));
// h2 = (int*)std::malloc(2*n*sizeof(int));
// v = (T*)std::malloc(n*sizeof(T));
// h3 = (T*)std::malloc(2*n*sizeof(T));
// M = n;
// if(fg) init(n);
// }
// inline void free(void){
// std::free(d);
// std::free(h1);
// std::free(h2);
// std::free(v);
// std::free(h3);
// }
// inline void walloc(const int n, void **mem=&wmem){
// walloc1d(&d, n, mem);
// walloc1d(&h1, 2*n, mem);
// walloc1d(&h2, 2*n, mem);
// walloc1d(&v, n, mem);
// walloc1d(&h3, 2*n, mem);
// M = n;
// }
// inline void walloc(const int n, const int fg, void **mem=&wmem){
// walloc1d(&d, n, mem);
// walloc1d(&h1, 2*n, mem);
// walloc1d(&h2, 2*n, mem);
// walloc1d(&v, n, mem);
// walloc1d(&h3, 2*n, mem);
// M = n;
// if(fg) init(n);
// }
// inline void init(const int n){
// int i;
// N = n;
// rep(i,n) d[i] = -1;
// sz = 0;
// snapsz = 0;
// }
// inline void init(void){
// init(M);
// }
// inline int get(int a){
// while(d[a]>=0) a=d[a];
// return a;
// }
// inline int connect(int a, int b){
// if(d[a]>=0) a=get(a);
// if(d[b]>=0) b=get(b);
// if(a==b) return 0;
// h1[sz] = a; h2[sz] = d[a]; h3[sz] = v[a]; sz++;
// h1[sz] = b; h2[sz] = d[b]; h3[sz] = v[b]; sz++;
// if(d[a] < d[b]) d[a] += d[b], d[b] = a, v[a] = rollbackUnionFind_md_func(v[a], v[b]);
// else d[b] += d[a], d[a] = b, v[b] = rollbackUnionFind_md_func(v[a], v[b]);
// return 1;
// }
// inline int operator()(int a){
// return get(a);
// }
// inline int operator()(int a, int b){
// return connect(a,b);
// }
// inline int& operator[](const int a){
// return d[a];
// }
// inline int size(int a){
// a = get(a);
// return -d[a];
// }
// inline int sizeList(int res[]){
// int i, sz=0;
// rep(i,N) if(d[i]<0) res[sz++] = -d[i];
// return sz;
// }
// inline int undo(void){
// if(sz==0) return 0;
// sz--; d[h1[sz]] = h2[sz]; v[h1[sz]] = h3[sz];
// sz--; d[h1[sz]] = h2[sz]; v[h1[sz]] = h3[sz];
// if(snapsz > sz) snapsz = sz;
// return 1;
// }
// inline void snapshot(void){
// snapsz = sz;
// }
// inline void rollback(void){
// while(snapsz < sz){
// sz--; d[h1[sz]] = h2[sz]; v[h1[sz]] = h3[sz];
// sz--; d[h1[sz]] = h2[sz]; v[h1[sz]] = h3[sz];
// }
// }
// inline T getVal(int a){
// a = get(a);
// return v[a];
// }
// inline void setVal(int a, T val){
// a = get(a);
// v[a] = val;
// }
// };
//
//
// rollbackUnionFind_md<RBMM> ruf1, ruf2;
// rollbackUnionFind_md<RBV> ruf;
//
// int invA[1d5], invB[1d5];
// int ftm[1d5], plc[1d5], ind[1d5];
// int liss[20][1d5];
// set<int> unused;
//
// int solve_uf_doit_sub(int i, int j){
// int res = 0;
// RBV v;
// if(ruf(i) != ruf(j)){
// v = ruf.getVal(i);
// res -= min(v.v, v.mx - v.mn + 1);
// v = ruf.getVal(j);
// res -= min(v.v, v.mx - v.mn + 1);
// ruf(i,j);
// v = ruf.getVal(i);
// res += min(v.v, v.mx - v.mn + 1);
// }
// return res;
// }
//
// int solve_uf_doit(int i){
// int x, res = 0;
// RBV v;
// x = invA[i];
// if(x-1 >= 0 && A[x-1] <= i){
// ruf1(x-1,x);
// if(ruf2(x-1) == ruf2(x)) res += solve_uf_doit_sub(x-1, x);
// }
// if(x+1 < N && A[x+1] <= i){
// ruf1(x,x+1);
// if(ruf2(x) == ruf2(x+1)) res += solve_uf_doit_sub(x, x+1);
// }
// x = invB[i];
// if(x-1 >= 0 && B[x-1] <= i){
// ruf2(x-1,x);
// if(ruf1(x-1) == ruf1(x)) res += solve_uf_doit_sub(x-1, x);
// }
// if(x+1 < N && B[x+1] <= i){
// ruf2(x,x+1);
// if(ruf1(x) == ruf1(x+1)) res += solve_uf_doit_sub(x, x+1);
// }
// return res;
// }
//
// void solve_uf_doit2(int i){
// int x;
// x = invA[i];
// if(x-1 >= 0 && A[x-1] <= i){
// ruf1(x-1,x);
// }
// if(x+1 < N && A[x+1] <= i){
// ruf1(x,x+1);
// }
// x = invB[i];
// if(x-1 >= 0 && B[x-1] <= i){
// ruf2(x-1,x);
// }
// if(x+1 < N && B[x+1] <= i){
// ruf2(x,x+1);
// }
// }
//
// void solve_sub(int s, int e, int sz, int *lis, int dep){
// int i, j, k, m, sz1, sz2, x, y;
// set<int>::iterator it;
//
// if(sz == 0){
// rep(i,s,e) solve_uf_doit2(i);
// return;
// }
//
// if(e-s==1){
// solve_uf_doit2(s);
// rep(i,sz){
// x = max(ruf1.getVal(invA[lis[i]]).mn, ruf2.getVal(invB[Z[lis[i]]]).mn);
// y = min(ruf1.getVal(invA[lis[i]]).mx, ruf2.getVal(invB[Z[lis[i]]]).mx);
// it = unused.lower_bound(x);
// if(it == unused.end() || *it > y) continue;
// ftm[lis[i]] = s;
// unused.erase(it);
// // wt(lis[i],s,x,y);
// }
// return;
// }
//
// m = (s + e) / 2;
// rep(i,s,m) solve_uf_doit2(i);
//
// sz1 = sz2 = 0;
// rep(i,sz){
// x = max(ruf1.getVal(invA[lis[i]]).mn, ruf2.getVal(invB[Z[lis[i]]]).mn);
// y = min(ruf1.getVal(invA[lis[i]]).mx, ruf2.getVal(invB[Z[lis[i]]]).mx);
// it = unused.lower_bound(x);
// if(x > y) continue;
// if(it == unused.end() || *it > y) continue;
// liss[dep+1][sz1++] = lis[i];
// }
//
// if(sz1){
// ruf1.rollback();
// ruf2.rollback();
// ruf.rollback();
//
// sz1 <?= 10 * (m - s);
// solve_sub(s,m,sz1,liss[dep+1],dep+1);
// }
// rep(i,sz) if(ftm[lis[i]] == -1) lis[sz2++] = lis[i];
//
// ruf1.snapshot();
// ruf2.snapshot();
// ruf.snapshot();
//
// solve_sub(m,e,sz2,lis,dep+1);
// rep(i,m,e) solve_uf_doit2(i);
// }
//
// VI solve(){
// int i, j, k;
// VI res(N);
// RBV v;
// int resval;
//
// ruf1.init(N);
// ruf2.init(N);
// ruf.init(N);
// rep(i,N) ruf1.setVal(i, {i,i});
// rep(i,N) ruf2.setVal(i, {i,i});
// rep(i,N) ruf.setVal(i, {i,i,0});
//
// rep(i,N) invA[A[i]] = i;
// rep(i,N) invB[B[i]] = i;
//
// rep(i,N) liss[0][i] = i;
// rep(i,N) ftm[i] = -1;
// rep(i,N) unused.insert(i);
// solve_sub(0, N, N, liss[0], 0);
//
// rep(i,N) ind[i] = i;
// sortA(N,ftm);
//
// // rep(i,N) wt(ind[i],ftm[i],plc[i]);
//
// k = 0;
// resval = 0;
// rep(i,N){
// resval += solve_uf_doit(i);
// while(k < N && ftm[k] == i){
// resval++;
// k++;
// }
// res[i] = resval;
// }
//
// return res;
// }
//
//
// int cnt[1d5];
// {
// Rand rnd;
// uf.walloc(1d5);
// uf1.walloc(1d5);
// uf2.walloc(1d5);
//
// ruf1.walloc(1d5);
// ruf2.walloc(1d5);
// ruf.walloc(1d5);
//
// N = cReader_ll(2, 1d5, '\n');
// rep(i,N) A[i] = cReader_ll(1, N, i==N-1?'\n':' ') - 1;
// rep(i,N) B[i] = cReader_ll(1, N, i==N-1?'\n':' ') - 1;
// rep(i,N) Z[i] = cReader_ll(1, N, i==N-1?'\n':' ') - 1;
//
// rep(i,N) cnt[i] = 0;
// rep(i,N) cnt[A[i]]++;
// rep(i,N) assert(cnt[i]==1);
// rep(i,N) cnt[i] = 0;
// rep(i,N) cnt[B[i]]++;
// rep(i,N) assert(cnt[i]==1);
// rep(i,N) cnt[i] = 0;
// rep(i,N) cnt[Z[i]]++;
// rep(i,N) assert(cnt[i]==1);
//
// cReader_eof();
//
// VI res;
// res = solve();
// wtLn(res(N));
// return 0;
//
// puts("");
// for(;;){
// VI r1, r2, r3;
// N = rnd.get(2,6);
// rep(i,N) A[i] = B[i] = Z[i] = i;
// random_shuffle(A,A+N);
// random_shuffle(B,B+N);
// random_shuffle(Z,Z+N);
//
// wt(N,":",A(N),":",B(N),":",Z(N));
// r1 = oobaka();
// r2 = baka();
// r3 = solve();
// wt(r1(N));
// wt(r2(N));
// wt(r3(N));
// assert(r1==r2);
// assert(r2==r3);
// }
//
// }