oj.uz

Submission #167660

# Submission time Handle Problem Language Result Execution time Memory
167660 2019-12-09T10:03:42 Z bicsi Matching (CEOI11_mat) C++14
100 / 100
 1459 ms 46056 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  int m, n; cin >> m >> n;
  
  vector<int> p(m), pos(m);
  for (int i = 0; i < m; ++i) { 
    int x; cin >> x; --x;
    p[x] = i;
    pos[i] = x;
  }

  vector<int> t(n);
  for (int i = 0; i < n; ++i)
    cin >> t[i];
  
  vector<int> lo(m, -1), hi(m, -1), pi(m + 1, -1);
  auto advance = [&](vector<int>& v, int i, int j) {
    while (j != -1) {
      if (lo[j] != -1 && v[i] < v[i - lo[j]]) { 
        j = pi[j]; 
        continue; 
      }
      if (hi[j] != -1 && v[i] > v[i - hi[j]]) { 
        j = pi[j]; 
        continue; 
      }
      break;
    }
    return j + 1;
  };
    
  vector<int> nxt(m, -1), prv(m, -1);
  for (int i = 0; i < m; ++i) {
    if (i > 0) prv[i] = i - 1;
    if (i + 1 < m) nxt[i] = i + 1;
  }

  for (int i = m - 1; i >= 0; --i) {
    int pr = prv[p[i]], nx = nxt[p[i]];
    if (pr != -1) lo[i] = i - pos[pr];
    if (nx != -1) hi[i] = i - pos[nx];
    if (pr != -1) nxt[pr] = nx;
    if (nx != -1) prv[nx] = pr;
  }

  for (int i = 0; i < m; ++i) {
    pi[i + 1] = advance(p, i, pi[i]);
  }

  vector<int> ans;
  int j = 0;
  for (int i = 0; i < n; ++i) {
    j = advance(t, i, j);
    if (j == m) {
      ans.push_back(i);
      j = pi[j];
    }
  }

  cout << ans.size() << endl;
  for (auto x : ans) {
    cout << x - m + 2 << " ";
  }
  cout << endl;

  return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 632 KB Output is correct
2 Correct 14 ms 632 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 632 KB Output is correct
2 Correct 15 ms 680 KB Output is correct
3 Correct 4 ms 376 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 3368 KB Output is correct
2 Correct 110 ms 2168 KB Output is correct
3 Correct 180 ms 3964 KB Output is correct
4 Correct 183 ms 4472 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 4068 KB Output is correct
2 Correct 150 ms 2696 KB Output is correct
3 Correct 158 ms 3704 KB Output is correct
4 Correct 131 ms 4464 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 4568 KB Output is correct
2 Correct 139 ms 3960 KB Output is correct
3 Correct 146 ms 3792 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 808 ms 11812 KB Output is correct
2 Correct 1459 ms 41216 KB Output is correct
3 Correct 582 ms 11896 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 13164 KB Output is correct
2 Correct 562 ms 5112 KB Output is correct
3 Correct 1223 ms 42408 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 7396 KB Output is correct
2 Correct 692 ms 16028 KB Output is correct
3 Correct 748 ms 6776 KB Output is correct
4 Correct 1209 ms 46056 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 8936 KB Output is correct
2 Correct 767 ms 6904 KB Output is correct
3 Correct 351 ms 7092 KB Output is correct
4 Correct 1230 ms 40532 KB Output is correct