fork download 
  1. import math
  2. def find(u, par):
  3.  
  4.     if par[u] != u:
  5.         par[u] = find(par[u], par)
  6.     return par[u]
  7.  
  8. def union(u, v, par, size):
  9.     u_root = find(u, par)
  10.     v_root = find(v, par)
  11.  
  12.     if u_root == v_root:
  13.         return 
  14.  
  15.  
  16.     if size[u_root] < size[v_root]:
  17.         par[u_root] = v_root
  18.         size[v_root] += size[u_root]
  19.     else:
  20.         par[v_root] = u_root
  21.         size[u_root] += size[v_root]
  22.  
  23. def ip():
  24.     return map(int,input().split())
  25.  
  26.  
  27.  
  28.  
  29. T=1
  30. T=int(input())
  31. for __ in range(T):
  32.     n=int(input())
  33.     a=list(ip())
  34.     b=list(ip())
  35.  
  36.     bfi={}  #bn,an-1,bn-2
  37.     afi={}  #an,bn-1,an-2
  38.     f=True
  39.     ans=0
  40.     for i in range(n-1,-1,-1):
  41.         # print()
  42.         # print("afi",afi)
  43.         # print("bfi",bfi)  
  44.         ai,bi=a[i],b[i]
  45.         if i==n-1:
  46.             if ai==bi:
  47.                 ans=i+1
  48.                 break
  49.             bfi[bi]=1
  50.             afi[ai]=1
  51.             afi,bfi=bfi,afi
  52.             continue
  53.  
  54.         if a[i]==b[i]:
  55.             ans=i+1
  56.             break
  57.  
  58.         #no del
  59.         if bi in afi or ai in bfi:
  60.             ans=i+1
  61.             break
  62.  
  63.         na,nb=a[i+1],b[i+1]
  64.         afi[nb]-=1
  65.         if afi[nb]==0:
  66.             del afi[nb]
  67.  
  68.         bfi[na]-=1
  69.         if bfi[na]==0:
  70.             del bfi[na]
  71.  
  72.         # print("afi after",afi)
  73.         # print("bfi after",bfi)
  74.         if ai in afi or bi in bfi:
  75.             ans=i+1
  76.             break
  77.         if na not in bfi:
  78.             bfi[na]=0
  79.         bfi[na]+=1
  80.  
  81.         if nb not in afi:
  82.             afi[nb]=0
  83.         afi[nb]+=1
  84.  
  85.  
  86.         if bi not in bfi:
  87.             bfi[bi]=0
  88.         bfi[bi]+=1
  89.  
  90.         if ai not in afi:
  91.             afi[ai]=0
  92.         afi[ai]+=1
  93.  
  94.         afi,bfi=bfi,afi 
  95.  
  96.     print(ans)
  97.  
  98.  
Success #stdin #stdout 0.13s 14164KB
comments (?)
stdin 
10
4
1 3 1 4
4 3 2 2
6
2 1 5 3 6 4
3 2 4 5 1 6
2
1 2
2 1
6
2 5 1 3 6 4
3 5 2 3 4 6
4
1 3 2 2
2 1 3 4
8
3 1 4 6 2 2 5 7
4 2 3 7 1 1 6 5
10
5 1 2 7 3 9 4 10 6 8
6 2 3 6 4 10 5 1 7 9
5
3 2 4 1 5
2 4 5 1 3
7
2 2 6 4 1 3 5
3 1 6 5 1 4 2
5
4 1 3 2 5
3 2 1 5 4
stdout 
3
3
0
4
3
5
6
4
5
2
https://ideone.com/Eya9Fl
language:
Python 3 (python  3.12)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!