#include <algorithm> #include <cstdio> #include <vector> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(c) (c).begin(),(c).end() #define SIZE(c) ((int)(c).size()) #define INT(x) int x; scanf("%d", &x) typedef vector<int> VI; typedef vector<bool> VB; const int mod = 1000000007; int a[300000], b[300000]; int r[600001]; int stab(const VI& v) { int n = SIZE(v), s = 1, d = 1, h = 0; REP(i,n-1) { int hh = v[i + 1] - v[i]; if (hh > 0) hh = 1; else if (hh < 0) hh = -1; if (hh == h) ++d; else { d = 2; h = hh; } s = max(s, d); } return s; } int f(int i1, int i2, int j1, int j2) { int n = i2 - i1, m = j2 - j1; int nm = n + m; VI v(nm); VB c(nm); REP(j,m) c[n + j] = 1; int mi = nm; do { int i = i1, j = j1; REP(ij,nm) if (c[ij]) v[ij] = b[j++]; else v[ij] = a[i++]; mi = min(mi, stab(v)); } while (next_permutation(ALL(c))); return mi; } int main() { INT(n); INT(m); REP(i,n) scanf("%d", &a[i]); REP(j,m) scanf("%d", &b[j]); REP(i1,n) FOR(i2,i1+1,n+1) REP(j1,m) FOR(j2,j1+1,m+1) { int x = f(i1, i2, j1, j2); ++r[x]; r[x] %= mod; } REP(i,n+m) { if (i) printf(" "); printf("%d", r[i + 1]); } printf("\n"); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | #include <algorithm> #include <cstdio> #include <vector> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(c) (c).begin(),(c).end() #define SIZE(c) ((int)(c).size()) #define INT(x) int x; scanf("%d", &x) typedef vector<int> VI; typedef vector<bool> VB; const int mod = 1000000007; int a[300000], b[300000]; int r[600001]; int stab(const VI& v) { int n = SIZE(v), s = 1, d = 1, h = 0; REP(i,n-1) { int hh = v[i + 1] - v[i]; if (hh > 0) hh = 1; else if (hh < 0) hh = -1; if (hh == h) ++d; else { d = 2; h = hh; } s = max(s, d); } return s; } int f(int i1, int i2, int j1, int j2) { int n = i2 - i1, m = j2 - j1; int nm = n + m; VI v(nm); VB c(nm); REP(j,m) c[n + j] = 1; int mi = nm; do { int i = i1, j = j1; REP(ij,nm) if (c[ij]) v[ij] = b[j++]; else v[ij] = a[i++]; mi = min(mi, stab(v)); } while (next_permutation(ALL(c))); return mi; } int main() { INT(n); INT(m); REP(i,n) scanf("%d", &a[i]); REP(j,m) scanf("%d", &b[j]); REP(i1,n) FOR(i2,i1+1,n+1) REP(j1,m) FOR(j2,j1+1,m+1) { int x = f(i1, i2, j1, j2); ++r[x]; r[x] %= mod; } REP(i,n+m) { if (i) printf(" "); printf("%d", r[i + 1]); } printf("\n"); } |