fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pii pair<int, int>
  4. #define double long double
  5. #define endl "\n"
  6. #define fi first
  7. #define se second
  8. #define mapa make_pair
  9. #define pushb push_back
  10. #define pushf push_front
  11. #define popb pop_back
  12. #define popf pop_front
  13. #define o_ ordered_
  14. #define ins insert
  15. #define era erase
  16. #define pqueue priority_queue
  17. #define CountBit __builtin_popcount
  18. #define PosBit __builtin_ctz
  19. #define minele min_element
  20. #define maxele max_element
  21. #define lb lower_bound // >=
  22. #define ub upper_bound // >
  23. #define debug cout << "NO ERROR", exit(0)
  24. #define FAST ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(x, i) (((x) >> (i)) & 1)
  27. #define ALL(v) v.begin(), v.end()
  28. #define SZ(v) (int)v.size()
  29. #define sqr(x) ((x) * (x))
  30.  
  31. template<class X, class Y>
  32.     bool minimize(X &x, const Y &y) {
  33.         if (x > y)
  34.         {
  35.             x = y;
  36.             return true;
  37.         }
  38.         return false;
  39.     }
  40. template<class X, class Y>
  41.     bool maximize(X &x, const Y &y) {
  42.         if (x < y)
  43.         {
  44.             x = y;
  45.             return true;
  46.         }
  47.         return false;
  48.     }
  49.  
  50. const int MOD = 1e9 + 7; //998244353;
  51. const int LOG = 18;
  52. const int INF = 1e9 + 7;
  53. const int d4x[4] = {-1, 1, 0, 0};
  54. const int d4y[4] = {0, 0, 1, -1};
  55. const char c4[4] = {'U', 'D', 'R', 'L'};
  56. const int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  57. const int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  58.  
  59. #define MAX 2005
  60.  
  61. int f[MAX][MAX], g[MAX][MAX], k, n, a[MAX], b[MAX];
  62. bool vis[MAX][MAX];
  63.  
  64. int getf(int l, int r, int x) {
  65.     minimize(r, n);
  66.     // cout << l << " " << r << " " << x << endl;
  67.     return f[r][x] - f[l - 1][x];
  68. }
  69. int getg(int l, int r, int x) {
  70.     return g[r][x] - g[l - 1][x];
  71. }
  72.  
  73. bool ok;
  74. void dfs(int l, int r) {
  75.     if (r - l + 1 == n) ok = true;
  76.     if (ok) return;
  77.     if (vis[l][r]) return;
  78.     vis[l][r] = true;
  79.     int x = l > 1 ? b[l - 1] : -1;
  80.     int y = r < 2 * n ? b[r + 1] : -1;
  81.     if (x != -1 && getf(1, r - l + 2 + k, x) > getg(l, r, x)) {
  82.         dfs(l - 1, r);
  83.     }
  84.     if (x != -1 && getf(1, r - l + 2 + k, y) > getg(l, r, y)) {
  85.         dfs(l, r + 1);
  86.     }
  87. }
  88.  
  89. bool check() {
  90.     memset(vis, false, sizeof vis);
  91.     ok = false;
  92.     for (int i = 1; i <= n; i++) if (getf(1, k + 1, b[i])) {
  93.         // cout << i << " " << b[i] << endl;
  94.         dfs(i + n, i + n);
  95.         dfs(i, i);
  96.     }
  97.     // cout << k << " " << ok << endl;
  98.     return ok;
  99. }
  100.  
  101.  
  102. void solve() {
  103.  
  104.     cin >> n;
  105.     for (int i = 1; i <= n; i++) cin >> a[i];
  106.     for (int i = 1; i <= n; i++) cin >> b[i];
  107.     for (int i = 1; i <= n; i++) b[n + i] = b[i];
  108.  
  109.     for (int i = 1; i <= n; i++) {
  110.         for (int j = 1; j <= n; j++) {
  111.             f[i][j] += f[i - 1][j];
  112.         }
  113.         f[i][a[i]]++;
  114.     }
  115.  
  116.    for (int i = 1; i <= 2 * n; i++) {
  117.         for (int j = 1; j <= n; j++) {
  118.             g[i][j] += g[i - 1][j];
  119.         }
  120.         g[i][b[i]]++;
  121.     }
  122.  
  123.  
  124.     int l = 0, r = n, mid, ans;
  125.     while (l <= r) {
  126.         mid = (l + r) / 2;
  127.         k = mid;
  128.         // cout << l << " " << r << endl;
  129.         if (check()) {
  130.             r = mid - 1;
  131.             ans = mid;
  132.         }
  133.         else l = mid + 1;
  134.         // debug;
  135.     }
  136.  
  137.     cout << ans << endl;
  138.  
  139.  
  140.  
  141.  
  142. }
  143.  
  144.  
  145. signed main() {
  146.  
  147.     freopen("flower.inp", "r", stdin);
  148.     freopen("flower.out", "w", stdout);
  149.  
  150.     FAST;
  151.     bool TestCase = 0;
  152.     int NumTest = 1;
  153.     // cin >> NumTest;
  154.     for (int i = 1; i <= NumTest; i++) {
  155.         if (TestCase) cout << "Case" << " " << i << ": ";
  156.         solve();
  157.     }
  158.  
  159. }
  160.  
Success #stdin #stdout 0.01s 7796KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cIYRzO
language:
C++14 (gcc 8.3)
created:
3 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!