Submission #347189

#	Time	Username	Problem	Language	Result	Execution time	Memory
347189		jklepec	Matching (CEOI11_mat)	C++11	Compilation error	0 ms	0 KiB

mat

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();
}

Compilation message (stderr)

mat.cpp:9:9: error: 'pair' does not name a type
    9 | typedef pair<int, int> point;
      |         ^~~~
mat.cpp:45:3: error: 'vector' does not name a type
   45 |   vector<int> L;
      |   ^~~~~~
mat.cpp: In member function 'void loga::init()':
mat.cpp:49:5: error: 'L' was not declared in this scope
   49 |     L.resize(MAXN);
      |     ^
mat.cpp: In member function 'void loga::upd(int, int)':
mat.cpp:53:34: error: 'L' was not declared in this scope
   53 |     for(; x < MAXN; x += x & -x) L[x] = add(L[x], v);
      |                                  ^
mat.cpp: In member function 'int loga::get(int)':
mat.cpp:57:46: error: 'L' was not declared in this scope
   57 |     for(; x > 0; x -= x & -x) ret = add(ret, L[x]);
      |                                              ^
mat.cpp: In function 'void solve()':
mat.cpp:106:3: error: 'vector' was not declared in this scope
  106 |   vector<int> sol;
      |   ^~~~~~
mat.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
  +++ |+#include <vector>
    1 | using namespace std;
mat.cpp:106:10: error: expected primary-expression before 'int'
  106 |   vector<int> sol;
      |          ^~~
mat.cpp:110:7: error: 'sol' was not declared in this scope; did you mean 'solve'?
  110 |       sol.push_back(i + 1);
      |       ^~~
      |       solve
mat.cpp:119:3: error: 'cout' was not declared in this scope
  119 |   cout << sz(sol) << endl;
      |   ^~~~
mat.cpp:1:1: note: 'std::cout' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
  +++ |+#include <iostream>
    1 | using namespace std;
mat.cpp:119:14: error: 'sol' was not declared in this scope; did you mean 'solve'?
  119 |   cout << sz(sol) << endl;
      |              ^~~
mat.cpp:6:22: note: in definition of macro 'sz'
    6 | #define sz(x) ((int) x.size())
      |                      ^
mat.cpp:119:22: error: 'endl' was not declared in this scope
  119 |   cout << sz(sol) << endl;
      |                      ^~~~
mat.cpp:1:1: note: 'std::endl' is defined in header '<ostream>'; did you forget to '#include <ostream>'?
  +++ |+#include <ostream>
    1 | using namespace std;
mat.cpp: In function 'int main()':
mat.cpp:127:3: error: 'ios_base' has not been declared
  127 |   ios_base::sync_with_stdio(false); cin.tie(0);
      |   ^~~~~~~~
mat.cpp:127:37: error: 'cin' was not declared in this scope
  127 |   ios_base::sync_with_stdio(false); cin.tie(0);
      |                                     ^~~
mat.cpp:127:37: note: 'std::cin' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
mat.cpp:141:3: error: 'vector' was not declared in this scope
  141 |   vector<point> v;
      |   ^~~~~~
mat.cpp:141:3: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
mat.cpp:141:10: error: 'point' was not declared in this scope; did you mean 'pot'?
  141 |   vector<point> v;
      |          ^~~~~
      |          pot
mat.cpp:141:17: error: 'v' was not declared in this scope
  141 |   vector<point> v;
      |                 ^
mat.cpp:148:3: error: 'sort' was not declared in this scope; did you mean 'short'?
  148 |   sort(v.begin(), v.end());
      |   ^~~~
      |   short