SRM649div1med:XorSequence
時間間に合うように実装したつもりだけどなんか時間かかってる・・・(最悪1.919sとかだった)なんでこんな時間かかるのかよくわからない(多分mapかなとは思っている)ので誰か教えて欲しいです。
問題:http://community.topcoder.com/stat?c=problem_statement&pm=13249&rd=16313
解法:div2hardと発想は同じ。ただ今回は配列Aのサイズが結構大きいのでそこは注意が必要。そこでどうするかというと、上からk番目のbitが同じもの同士でグループ分けしてそのそれぞれについて上からk+1番目のBのbitを0にするか1にするかを決定していけば良い。
以下ソースコード
ll getReverse(const vector<int>& a) { ll sum = 0; ll ans = 0; int n = a.size(); for (int i = 0; i < n; i++) { if (a[i] > 0) ans += sum; else sum++; } return ans; } class XorSequence { public: ll getmax(int N, int sz, int A0, int A1, int P, int Q, int R) { vector<ll> A(sz); A[0] = A0; A[1] = A1; for (int i = 2; i < sz; i++) { A[i] = (A[i-2]*P + A[i-1]*Q + R) % N; } int K = __builtin_popcount(N-1); ll ret = 0; for (int k = K; k >= 1; k--) { vector<ll> cmp(2); map<ll, vector<int> > m; for (int i = 0; i < sz; i++) { m[(A[i]>>k)].push_back((A[i]>>(k-1))&1); } for (auto el : m) { vector<int> p = el.second; cmp[0] += getReverse(p); for (int i = 0; i < (int)p.size(); i++) p[i] ^= 1; cmp[1] += getReverse(p); } ret += max(cmp[0], cmp[1]); } return ret; } };