oj.uz

답안 #347190

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
347190 2021-01-12T08:52:07 Z jklepec Matching (CEOI11_mat) C++11
100 / 100
 786 ms 40300 KB 
#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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 7 ms 8172 KB Output is correct
4 Correct 6 ms 8320 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 8556 KB Output is correct
2 Correct 13 ms 8556 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 8556 KB Output is correct
2 Correct 15 ms 8556 KB Output is correct
3 Correct 7 ms 8300 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 12012 KB Output is correct
2 Correct 87 ms 11884 KB Output is correct
3 Correct 116 ms 12908 KB Output is correct
4 Correct 117 ms 13132 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 12780 KB Output is correct
2 Correct 122 ms 12524 KB Output is correct
3 Correct 106 ms 12908 KB Output is correct
4 Correct 105 ms 14056 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 12996 KB Output is correct
2 Correct 86 ms 12268 KB Output is correct
3 Correct 119 ms 12576 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 548 ms 31676 KB Output is correct
2 Correct 718 ms 40300 KB Output is correct
3 Correct 509 ms 25068 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 552 ms 30828 KB Output is correct
2 Correct 764 ms 26732 KB Output is correct
3 Correct 786 ms 36868 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 596 ms 29224 KB Output is correct
2 Correct 514 ms 37664 KB Output is correct
3 Correct 638 ms 29932 KB Output is correct
4 Correct 400 ms 38380 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 502 ms 29952 KB Output is correct
2 Correct 639 ms 30468 KB Output is correct
3 Correct 216 ms 18668 KB Output is correct
4 Correct 482 ms 38380 KB Output is correct