結果
問題 | No.1245 ANDORゲーム(calc) |
ユーザー |
![]() |
提出日時 | 2020-10-03 00:15:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 483 ms / 2,000 ms |
コード長 | 1,793 bytes |
コンパイル時間 | 1,862 ms |
コンパイル使用メモリ | 184,096 KB |
実行使用メモリ | 43,200 KB |
最終ジャッジ日時 | 2024-07-18 00:55:16 |
合計ジャッジ時間 | 10,982 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for (int i = 0; i < (n); ++i)#define chmax(a, b) a = max(a, b)#define chmin(a, b) a = min(a, b)#define all(x) (x).begin(), (x).end()#define int long longusing namespace std;using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;signed main() {int n, q;cin >> n >> q;VI a(n);rep(i, n) cin >> a[i];string st;cin >> st;vector<vector<P>> d(30);ll s = 0;vector<ll> dif(n);rep(i, n) {int t = 0;rep(k, 30) {if (st[i] == '0' && (a[i] >> k & 1) == 0) {if (d[k].empty()) {t -= 1 << k;} else if (d[k].back().second == 1) {t -= 1 << k;}d[k].emplace_back(i, 0);} else if (st[i] == '1' && (a[i] >> k & 1) == 1) {if (d[k].empty()) {t += 1 << k;} else if (d[k].back().second == 0) {t += 1 << k;}d[k].emplace_back(i, 1);}}s += abs(t);dif[i] = t;}rep(_, q) {int ti;cin >> ti;ll ans = s;map<int, int> m;rep(k, 30) {if (d[k].empty()) continue;int i = d[k][0].first, c = d[k][0].second;if (c == (ti >> k & 1)) {if (m.find(i) == m.end()) {m[i] = dif[i];}if (c == 1) m[i] -= 1 << k;else m[i] += 1 << k;}}for(auto p: m) {int i, t;tie(i, t) = p;ans += -abs(dif[i]) + abs(t);}cout << ans << endl;}}