제출 #347961

#제출 시각아이디문제언어결과실행 시간메모리
347961lovro_nidogon1Matching (CEOI11_mat)C++14
63 / 100
1101 ms65540 KiB
#include<bits/stdc++.h> #define breturn return #define ll long long using namespace std; const ll b = 31337; const ll mod = 1e9 + 7; const int maxn = 1e6 + 69; ll n, m,bn, arr[maxn], a, che[maxn], chash, rhash, tour[4194310], bre, act[4194310], cnt; vector<pair<ll, ll> > perm; vector<ll> odg; map<ll, ll> maph; ll mul(ll x, ll y) { breturn (x * y)%mod; } ll ad(ll x, ll y) { if(x + y >= mod) breturn x + y - mod; else if(x + y < 0) breturn x + y + mod; breturn x + y; } ll quer(ll ax, ll bx, ll x = 1, ll l = 0, ll r = bn - 1) { if(l > bx or r < ax) breturn 0; if(l >= ax and r <= bx) breturn tour[x]; ll mid = (l + r)/2; breturn ad(quer(ax, bx, x * 2, l, mid), quer(ax, bx, x * 2 + 1, mid + 1, r)); } ll smol(ll ax, ll bx, ll x = 1, ll l = 0, ll r = bn - 1) { if(l > bx or r < ax) breturn 0; if(l >= ax and r <= bx) breturn act[x]; ll mid = (l + r)/2; breturn smol(ax, bx, x * 2, l, mid) + smol(ax, bx, x * 2 + 1, mid + 1, r); } ll bp(ll p, ll x) { if(x == 0) breturn 1; if(x%2) breturn mul(bp(p, x - 1), p); ll xx = bp(p, x/2); breturn mul(xx, xx); } int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n >> m; bn = (1 << ((int)log2(m - 1) + 1)); for(int i = 0; i < n; i++) { cin >> a; arr[a - 1] = i + 1; } for(int i = 0; i < n; i++) { chash = mul(chash, b); chash = ad(chash, arr[i]); } for(int i = 0; i < m; i++) { cin >> arr[i]; perm.push_back({arr[i], i}); } sort(perm.begin(), perm.end()); for(int i = 0; i < perm.size(); i++) maph[perm[i].first] = i; perm.clear(); perm.shrink_to_fit(); for(int i = 0; i < n; i++) perm.push_back({arr[i], i}); sort(perm.begin(), perm.end()); for(int i = 0; i < n; i++) che[perm[i].second] = i + 1; for(int i = 0; i < n; i++) { rhash = mul(rhash, b); rhash = ad(rhash, che[i]); tour[maph[arr[i]] + bn] = bp(b, n - i - 1); act[maph[arr[i]] + bn] = 1; } perm.clear(); perm.shrink_to_fit(); for(int i = bn - 1; i > 0; i--) tour[i] = ad(tour[i * 2], tour[i * 2 +1]), act[i] = act[i * 2] + act[i * 2 + 1]; if(rhash == chash) odg.push_back(1); for(int i = n; i < m; i++) { ll x = maph[arr[i - n]]; rhash = ad(rhash, -mul(smol(0, x), bp(b, n - 1))); rhash = ad(rhash, -mul(quer(x + 1, bn - 1), bp(b, cnt))); x += bn; act[x] = 0; tour[x] = 0; x /= 2; while(x) act[x] = act[x * 2] + act[x * 2 + 1], tour[x] = ad(tour[x * 2], tour[x * 2 + 1]), x /= 2; x = maph[arr[i]]; rhash = ad(rhash, mul(quer(x + 1, bn - 1), bp(b, cnt))); cnt ++; rhash = mul(rhash, b); rhash = ad(rhash, smol(0, x) + 1); x += bn; act[x] = 1; tour[x] = bp(bp(b, cnt), mod - 2); x /= 2; while(x) act[x] = act[x * 2] + act[x * 2 + 1], tour[x] = ad(tour[x * 2], tour[x * 2 + 1]), x /= 2; if(rhash == chash) odg.push_back(i - n + 2); } cout << odg.size() << '\n'; for(int i = 0; i < odg.size(); i++) cout << odg[i] << " "; }

컴파일 시 표준 에러 (stderr) 메시지

mat.cpp: In function 'int main()':
mat.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i = 0; i < perm.size(); i++) maph[perm[i].first] = i;
      |                 ~~^~~~~~~~~~~~~
mat.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for(int i = 0; i < odg.size(); i++) cout << odg[i] << " ";
      |                 ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...