fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. /*
  6.     ALTERNATING OPERATIONS:
  7.     op[1] => odd => delete from front
  8.     op[2] => even => delete from back
  9.     op[3] => odd => delete from front
  10.     .
  11.     .
  12.     .
  13.     op[n] => delete last element from arr
  14.  
  15.     element closest to center of arr is the one that requires the most operations to delete => ans
  16.  
  17.     EXAMPLE:
  18.     8 3
  19.     1 2 3 4 5 5 5 6
  20.     2 5 6
  21.     
  22.     middle at indices 3,4
  23.     2 => at index 1 => dist = 3-1 = 2
  24.     5 => at index 4 => dist = 4-4 = 0
  25.     6 => at index 7 => dist = 7-4 = 3
  26.     element 5 is closest to center at index 4
  27.     
  28.     OPERATIONS:
  29.     1 => remove 1 & 6
  30.     2 => remove 2 & 5
  31.     3 => remove 3 & 5
  32.     4 => remove 4 & 5
  33.     total elements removed = 8
  34.  
  35.     Simulate using two pointers
  36.  
  37.     OR:
  38.  
  39.     for alternating operations:
  40.     
  41.     FROM LEFT:
  42.     element at index i = 0, deletion requires 1 operation
  43.     element at index i = 1, deletion requires 3 operations => 0, n-1, 1
  44.     element at index i = 2, deletion requires 5 operations => 0, n-1, 1, n-2, 2
  45.     .
  46.     .
  47.     .
  48.     deleting from left: 2*(i+1)-1
  49.  
  50.     FROM RIGHT:
  51.     element at index i = n-1, deletion requires 2 operations
  52.     element at index i = n-2, deletion requires 4 operations => 0, n-1, 1, n-2
  53.     element at index i = n-3, deletion requires 6 operations => 0, n-1, 1, n-2, 2, n-3
  54.     .
  55.     .
  56.     .
  57.     deleting from right: 2*(n-i)
  58. */
  59.  
  60. void mohemmat() {
  61.     int n, m; cin >> n >> m;
  62.     vector<int> a(n);
  63.     unordered_set<int> b;
  64.  
  65.     for (int i = 0; i < n; i++) {
  66.         cin >> a[i];
  67.     }
  68.  
  69.     for (int i = 0; i < m; i++) {
  70.         int x; cin >> x;
  71.         b.insert(x);
  72.     }
  73.  
  74.     // FROM CLAUDE
  75.     int ans = 0;
  76.     for (int i = 0; i < n; i++) {
  77.         if (b.count(a[i])) {
  78.             int cost = min(2*(i+1)-1, 2*(n-i));
  79.             /*
  80.                 0-index i:
  81.                 COST OF DELETION FROM LEFT: 2*(i+1)-1
  82.                 COST OF DELETION FROM RIGHT: 2*(n-i)
  83.             */
  84.             ans = max(ans, cost);
  85.         }
  86.     }
  87.     cout << ans << '\n';
  88. }
  89.  
  90. int main() {
  91.     ios::sync_with_stdio(false);
  92.     cin.tie(nullptr);
  93.     cout.tie(nullptr);
  94.  
  95.     int t = 1;
  96.     cin >> t;
  97.     while (t--) {mohemmat();}
  98.  
  99.     return 0;
  100. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/h5JXgX
language:
C++ (gcc 8.3)
created:
15 hours 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!