Submission #347260

#TimeUsernameProblemLanguageResultExecution timeMemory
347260Harry464Matching (CEOI11_mat)C++14
100 / 100
1311 ms65536 KiB
#include <iostream> #include <vector> #include <cmath> #include <map> #include <algorithm> #include <set> using namespace std; typedef long long ll; ll mod = 1000000007; ll n, m; vector <ll> fen(1000001,0); vector <int> brojevi(1000001,0); ll sum(ll k){ ll s = 0; while (k >= 1){ s += fen[k]; s %= mod; k -= k&-k; } return s; } void add(ll k, ll x){ while (k <= m){ fen[k] += x; k += k&-k; } } int sum2(int k){ int s = 0; while (k >= 1){ s += brojevi[k]; k -= k&-k; } return s; } void add2(ll k, ll x){ while (k <= m){ brojevi[k] += x; k += k&-k; } } int main() { cin >> n >> m; vector <ll> a(n); vector <ll> b(m); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> b[i]; vector <ll> t = a; for (int i = 0; i < n; i++) a[t[i]-1] = i + 1; vector <pair <ll,ll> > k(m); for (int i = 0; i < m; i++) k[i].first = b[i], k[i].second = i; sort(k.begin(), k.end()); for (int i = 0; i < m; i++) b[k[i].second] = i + 1; ll poredi = 0; vector <ll> pows(1,1); for (int i = 1; i <= 1000000; i++) pows.push_back((pows[i-1]*67)%mod); for (int i = 0; i < n; i++) poredi += (a[i]*pows[i])%mod, poredi %= mod; ll hes = 0; set <ll> tren; for (int i = 0; i < n; i++) add2(b[i],1); vector <ll> rjesenja; for (int i = 0; i < n; i++){ add(b[i], pows[i]); ll val = sum2(b[i]); hes += (val*pows[i])%mod, hes %= mod; } if (hes == poredi) rjesenja.push_back(1); for (int i = n; i < m; i++){ poredi *= 67, poredi %= mod; ll o1 = sum(m) - sum(b[i-n]); while (o1 < 0) o1 += mod; ll o2 = (sum2(b[i-n])*pows[i-n])%mod; add2(b[i-n], -1); add(b[i-n], -(sum(b[i-n])-sum(b[i-n]-1))); add2(b[i],1); add(b[i], pows[i]); ll d1 = (sum2(b[i])*pows[i])%mod; ll d2 = sum(m) - sum(b[i]); while (d2 < mod) d2 += mod; hes += (d1 + d2)%mod; hes %= mod; hes -= (o1 + o2)%mod; while (hes < 0) hes += mod; hes %= mod; //cout << poredi << " " << hes << endl; if (poredi == hes) rjesenja.push_back(i - n + 2); } cout << rjesenja.size() << endl; for (int i = 0; i < rjesenja.size(); i++) cout << rjesenja[i] << " "; }

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (int i = 0; i < rjesenja.size(); 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...