제출 #347257

#제출 시각아이디문제언어결과실행 시간메모리
347257Harry464Matching (CEOI11_mat)C++14
63 / 100
773 ms65540 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 <ll> 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; } } ll sum2(ll k){ ll 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; map <ll, ll> key; vector <ll> k = b; sort(k.begin(), k.end()); for (int i = 0; i < m; i++) key[k[i]] = i + 1; for (int i = 0; i < m; i++) b[i] = key[b[i]]; 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] << " "; }

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

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