Submission #347190

#	Time	Username	Problem	Language	Result	Execution time	Memory
347190		jklepec	Matching (CEOI11_mat)	C++11	100 / 100	786 ms	40300 KiB

mat

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 1e6 + 5, mod = 1e9 + 7, B = 32452867;

int invB;

int add(int x, int y) {
  x += y;
  if(x >= mod) return x - mod;
  return x;
}
int mul(int x, int y) {
  return (ll) x * y % mod;
}
int sub(int x, int y) {
  x -= y;
  if(x < 0) return x + mod;
  return x;
}
int pot(int x, int e) {
  int ret = x; e --;
  while(e) {
    if(e & 1) ret = mul(ret, x);
    x = mul(x, x);
    e /= 2;
  }
  return ret;
}

int p[MAXN];
int a[MAXN];

int temporary_hash;

struct loga {
  int uk;
  vector<int> L;

  void init() {
    uk = 0;
    L.resize(MAXN);
  }
  void upd(int x, int v) {
    uk = add(uk, v);
    for(; x < MAXN; x += x & -x) L[x] = add(L[x], v);
  }
  int get(int x) {
    int ret = 0;
    for(; x > 0; x -= x & -x) ret = add(ret, L[x]);
    return ret;
  }
} active, poly;

int glob, invglob;

void Append(int x) {
  int &h = temporary_hash;

  glob = mul(glob, B);
  invglob = mul(invglob, invB);

  h = mul(h, B);
  h = add(h, mul(sub(poly.uk, poly.get(x)), glob));

  int new_value = active.get(x) + 1;
  h = add(h, new_value);

  poly.upd(x, invglob);
  active.upd(x, 1);
}

void Del(int x) {
  int &h = temporary_hash;

  int Base = sub(poly.get(x), poly.get(x - 1));
  int Value = active.get(x);

  h = sub(h, mul(Value, mul(Base, glob)));
  h = sub(h, mul(sub(poly.uk, poly.get(x)), glob));

  poly.upd(x, sub(0, Base));
  active.upd(x, -1);
}

int h;
int n, m;

void solve() {
  poly.init();
  active.init();

  glob = invglob = 1;

  REP(i, n) {
    Append(a[i]);
  }

  vector<int> sol;

  REP(i, m - n + 1) {
    if(temporary_hash == h) {
      sol.push_back(i + 1);
    }

    if(i != m - n) {
      Append(a[i + n]);
      Del(a[i]);
    }
  }

  cout << sz(sol) << endl;
  for(auto x: sol) {
    cout << x << " ";
  }

}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  invB = pot(B, mod - 2);

  cin >> n >> m;

  REP(i, n) {
    int x; cin >> x;
    p[x - 1] = i + 1;
  }
  REP(i, n) {
    h = mul(h, B);
    h = add(h, p[i]);
  }

  vector<point> v;
  v.reserve(m);

  REP(i, m) {
    cin >> a[i];
    v.push_back({a[i], i});
  }
  sort(v.begin(), v.end());

  REP(i, sz(v)) {
    a[v[i].second] = i + 1;
  }

  solve();
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10