#P3740. pku2842 N-dimension Matching N维匹配

pku2842 N-dimension Matching N维匹配

题目描述

给定两个 NN 维整数数组 S,TS,T,其各维长度分别为 (a1,…,aN)(a_1,\ldots,a_N) 和 (b1,…,bN)(b_1,\ldots,b_N)。每一维的下标从 11 开始。

设 p=(p1,…,pN)p=(p_1,\ldots,p_N),且每维满足 1≤pd≤ad−bd+11\le p_d\le a_d-b_d+1。若对于所有满足 1≤id≤bd1\le i_d\le b_d 的下标 (i1,…,iN)(i_1,\ldots,i_N) 都有

T[i1,…,iN]=S[p1+i1−1,…,pN+iN−1],T[i_1,\ldots,i_N]=S[p_1+i_1-1,\ldots,p_N+i_N-1],

则称 pp 为一个匹配位置。求字典序最小的匹配位置。

输入格式

第一行一个整数 NN。第二、三行分别是 NN 个整数 a1,…,aNa_1,\ldots,a_N、b1,…,bNb_1,\ldots,b_N。

第四行给出 SS 的 ∏dad\prod_d a_d 个元素,第五行给出 TT 的 ∏dbd\prod_d b_d 个元素。两个数组的元素都按下标元组的字典序列出,第一维变化最慢,最后一维变化最快。

输出格式

输出 NN 个整数 p1,…,pNp_1,\ldots,p_N,表示字典序最小的匹配位置。

数据范围

1≤N≤101\le N\le10,1≤bd≤ad1\le b_d\le a_d,两个数组各自的元素总数不超过 500000500000。本站评测保证至少有一个匹配位置,且元素均为 11 或 22。

样例

2
4 4
2 2
3 2 1 1 2 2 2 1 1 2 2 2 1 1 2 2
2 2 2 2
2 2

题目来源