QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#571683 | #9351. Game Store | real_sigma_team# | RE | 82ms | 171692kb | C++17 | 2.9kb | 2024-09-18 03:39:55 | 2024-09-18 03:39:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve();
int32_t main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
constexpr int K = 729 * 9;
int clc[K][K];
__int128_t deg3[61];
__int128_t _xor3(__int128_t a, __int128_t b) {
__int128_t res = 0, i3 = 1;
while (a || b) {
res += ((a % 3 + b % 3) % 3) * i3;
i3 *= 3;
a /= 3;
b /= 3;
}
return res;
}
__int128_t __xor3(__int128_t a, __int128_t b) {
__int128_t res = 0, i3 = 1;
while (a || b) {
res += clc[a % K][b % K] * i3;
i3 *= K;
a /= K;
b /= K;
}
return res;
}
__int128_t xor3(__int128_t a, __int128_t b) {
auto x1 = _xor3(a, b);
auto x2 = __xor3(a, b);
assert(x1 == x2);
return x1;
}
__int128_t mndeg3(__int128_t x) {
if (x == 0) return 0;
int l = 0, r = 60;
while (r != l) {
int m = (r + l) / 2 + 1;
if (deg3[m] <= x) {
l = m;
} else {
r = m - 1;
}
}
return deg3[l];
}
void solve() {
deg3[0] = 1;
for (int i = 1; i < 61; i++) {
deg3[i] = deg3[i - 1] * 3;
}
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
if (i < 3 || j < 3) {
clc[i][j] = _xor3(i, j);
} else {
clc[i][j] = clc[i / 3][j / 3] * 3 + (i % 3 + j % 3) % 3;
}
}
}
int n;
cin >> n;
ll last = 0;
vector<pair<__int128_t, int>> base;
for (int i = 0; i < n; i++) {
ll x, y;
cin >> x >> y;
x ^= last;
y ^= last;
__int128_t i3 = 1;
__int128_t a = 0;
for (int j = 0; j < 60; j++) {
if ((1ll << j) & x) {
a += i3;
}
i3 *= 3;
}
int b = y;
int ind = 0;
pair<int, int> mx = {0, 0};
pair<__int128_t, int> oink;
for (auto [v, c] : base) {
if (mndeg3(a) <= mndeg3(v)) {
if (make_pair(b - c, ind) > mx) {
mx = make_pair(b - c, ind);
oink = {a, b};
}
while (mndeg3(a) == mndeg3(v)) {
a = xor3(a, v);
}
} else {
break;
}
ind++;
}
for (int j = 0; j + 1 < base.size(); ++j) {
assert(mndeg3(base[j].first) > mndeg3(base[j + 1].first));
}
if (a) {
base.emplace(base.begin() + ind, a, b);
last += b;
} else if (mx.first > 0) {
last += mx.first;
base[mx.second] = oink;
}
cout << last << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 82ms
memory: 171692kb
input:
3 1 4 6 7 4 13
output:
4 7 14
result:
ok 3 lines
Test #2:
score: -100
Runtime Error
input:
500000 395134631858718935 964539556 125290790696511447 743741881 68785955678986648 1867726875 774218610629433714 1107843806 251011758189826329 3218789432 712376502291877860 3368474950 237512969552427655 3307057592 26026853208103063 3366794857 904189246433646740 3824475130 105677592268903953 50111856...