QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #867022 | #9684. 倾诉 | Tony2 | Compile Error | / | / | C++14 | 12.5kb | 2025-01-23 00:33:35 | 2025-01-23 00:33:36 |
Judging History
This is the latest submission verdict.
- [2025-01-23 00:33:36]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2025-01-23 00:33:35]
- Submitted
answer
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ld = long double;
const int N = 2e4 + 35, lim = 22, mod1 = 998244353, mod2 = 1e9 + 7, inf = 1e9 + 2;
mt19937 rnd(0);
int tt, n, K, a[N], cur[N], prehigh[N], pre[N], id[N];
int log2n, st[N][25];
int pre2[N];
ld pw[N * 2], sum[N];
int pw1[N * 2], pw2[N * 2];
int rt[N];
struct Msg{
int len, a1, a2;
Msg(){}
Msg(int len, int a1, int a2) : len(len), a1(a1), a2(a2) {}
friend Msg operator + (const Msg &a, const Msg &b){
return Msg(a.len + b.len, (a.a1 + 1ll * b.a1 * pw1[a.len]) % mod1, (a.a2 + 1ll * b.a2 * pw2[a.len]) % mod2);
}
}all1[N];
bool same(const Msg &a, const Msg &b){
return a.len == b.len && a.a1 == b.a1 && a.a2 == b.a2;
}
struct tree{
#define mid ((l + r) >> 1)
int tot;
struct node{
int ls, rs;
Msg msg;
}a[N * 30];
void build(int &p, int l, int r){
p = ++tot;
if (l == r){
a[p].msg = Msg(1, 0, 0);
return;
}
build(a[p].ls, l, mid);
build(a[p].rs, mid + 1, r);
a[p].msg = a[a[p].ls].msg + a[a[p].rs].msg;
}
void add(int &p, int o, int l, int r, int s, int k){
a[p = ++tot] = a[o];
if (l == r){
a[p].msg = Msg(1, k, k);
return;
}
if (s <= mid) add(a[p].ls, a[o].ls, l, mid, s, k);
else add(a[p].rs, a[o].rs, mid + 1, r, s, k);
a[p].msg = a[a[p].ls].msg + a[a[p].rs].msg;
}
Msg ask(int p, int l, int r, int s, int t){
if (s <= l && r <= t) return a[p].msg;
Msg res(0, 0, 0);
if (s <= mid) res = res + ask(a[p].ls, l, mid, s, t);
if (t > mid) res = res + ask(a[p].rs, mid + 1, r, s, t);
return res;
}
Msg ask(int p, int l, int r, int s){
return ask(p, l, r, s, s);
}
int askr(int p, int l, int r, int s){
if (a[p].msg.a1 == 0 && a[p].msg.a2 == 0) return 0;
if (s <= l){
if (l == r) return l;
int res = askr(a[p].ls, l, mid, s);
if (res) return res;
else return askr(a[p].rs, mid + 1, r, s);
}
if (s <= mid){
int res = askr(a[p].ls, l, mid, s);
if (res) return res;
else return askr(a[p].rs, mid + 1, r, s);
}else return askr(a[p].rs, mid + 1, r, s);
}
int askl1(int p, int l, int r, int s){
if (a[p].msg.a1 == 0 && a[p].msg.a2 == 0) return 0;
if (r <= s){
if (l == r) return l;
int res = askl1(a[p].rs, mid + 1, r, s);
if (res) return res;
else return askl1(a[p].ls, l, mid, s);
}
if (mid < s){
int res = askl1(a[p].rs, mid + 1, r, s);
if (res) return res;
else return askl1(a[p].ls, l, mid, s);
}else return askl1(a[p].ls, l, mid, s);
}
int askl0(int p, int l, int r, int s){
if (same(a[p].msg, all1[r - l + 1])) return 0;
if (r <= s){
if (l == r) return l;
int res = askl0(a[p].rs, mid + 1, r, s);
if (res) return res;
else return askl0(a[p].ls, l, mid, s);
}
if (mid < s){
int res = askl0(a[p].rs, mid + 1, r, s);
if (res) return res;
else return askl0(a[p].ls, l, mid, s);
}else return askl0(a[p].ls, l, mid, s);
}
#undef mid
}T;
int lcp(int i, int j){
int p1 = prehigh[i], p2 = prehigh[j];
int l = 1, r = min(p1, p2), mid;
while (l <= r){
mid = (l + r) >> 1;
if (same(T.ask(rt[i], 1, n + lim, p1 - mid + 1, p1), T.ask(rt[j], 1, n + lim, p2 - mid + 1, p2))) l = mid + 1;
else r = mid - 1;
}
return r;
}
int lcp2(int i, int j){
if (i == j) return prehigh[i];
else{
int l = min(id[i], id[j]), r = max(id[i], id[j]) - 1;
int t = 31 ^ __builtin_clz(r - l + 1);
return min(st[l][t], st[r - (1 << t) + 1][t]);
}
}
template<typename T> cmp(T a, T b){
if (a > b) return 1;
else if (a == b) return 0;
else return -1;
}
int cmp_pre(int i, int j){
int p1 = prehigh[i], p2 = prehigh[j];
int r = lcp(i, j);
int num1 = p1 == r ? 0 : T.ask(rt[i], 1, n + lim, p1 - r).a1;
int num2 = p2 == r ? 0 : T.ask(rt[j], 1, n + lim, p2 - r).a1;
return cmp(num1, num2);
}
struct Msg2{
int tp, len;
int num;//单个数字 0 连续相同 1
int R, r;//原本区间 2
Msg2(){}
Msg2(int tp, int len, int num, int R, int r) : tp(tp), len(len), num(num), R(R), r(r) {}
};
pair<vector<Msg2>, int> getMsg(int l, int r){
//1 ~ l-1 l ~ l+lim-1 l+lim ~ p p+1 ~ prehigh[r1]
int a = T.ask(rt[r], 1, n + lim, l, l + lim - 1).a1, b = pre2[l];
if (a >= b) return make_pair(vector<Msg2>{Msg2(0, lim, a - b, 0, 0), Msg2(2, prehigh[r] - (l + lim - 1), 0, r, prehigh[r])}, prehigh[r]);
else{
int p = T.askr(rt[r], 1, n + lim, l + lim);
if (p < prehigh[r]) return make_pair(vector<Msg2>{Msg2(0, lim, (1 << lim) + a - b, 0, 0), Msg2(1, p - (l + lim), 1, 0, 0), Msg2(1, 1, 0, 0, 0), Msg2(2, prehigh[r] - p, 0, r, prehigh[r])}, prehigh[r]);
else return make_pair(vector<Msg2>{Msg2(0, lim, (1 << lim) + a - b, 0, 0), Msg2(1, p - (l + lim), 1, 0, 0)}, prehigh[r] - 1);
}
}
int cmp_seg(int l1, int r1, int l2, int r2, int k){//left >> k 缩小
if (min(r1 - l1, r2 - l2) < lim * 2){
ld lft = sum[r1] - sum[l1 - 1] * pw[r1 - l1 + 1], rgt = sum[r2] - sum[l2 - 1] * pw[r2 - l2 + 1];
int k2 = r2 - r1 + k;
if (k2 >= 0) return cmp(lft * pw[k2], rgt);
else return cmp(lft, rgt * pw[-k2]);
}else{
int _lcp = lcp2(r1, r2);
auto [vec1, ph1] = getMsg(l1, r1);
auto [vec2, ph2] = getMsg(l2, r2);
if (ph1 - k != ph2) return cmp(ph1 - k, ph2);
{
int len1 = ph1 - l1, len2 = ph2 - l2;
if (len1 < len2) vec1.insert(vec1.begin(), Msg2(1, len2 - len1, 0, 0, 0));
else vec2.insert(vec2.begin(), Msg2(1, len1 - len2, 0, 0, 0));
}
if (vec1.back().tp == 2 && vec2.back().tp == 2 && _lcp < min(vec1.back().len, vec2.back().len))
return cmp(T.ask(rt[r1], 1, n + lim, ph1 - _lcp).a1, T.ask(rt[r2], 1, n + lim, ph2 - _lcp).a1);
while (!vec1.empty() && !vec2.empty()){
Msg2 msg1 = vec1.back(), msg2 = vec2.back();
vec1.pop_back(), vec2.pop_back();
if (msg1.len == 0) vec2.push_back(msg2);
else if (msg2.len == 0) vec1.push_back(msg1);
else{
int flg = 1;
if (msg1.len < msg2.len){
flg = -1;
swap(msg1, msg2);
}
int len2 = msg1.len - msg2.len;
Msg2 msg3;
if (msg1.tp == 0){
msg3 = Msg2(0, len2, msg1.num & ((1 << len2) - 1), 0, 0);
int num2;
if (msg2.tp == 0) num2 = msg2.num;
else if (msg2.tp == 1) num2 = msg2.num ? ((1 << msg2.len) - 1) : 0;
else num2 = T.ask(rt[msg2.R], 1, n + lim, msg2.r - msg2.len + 1, msg2.r).a1;
if ((msg1.num >> len2) != num2) return cmp(msg1.num >> len2, num2) * flg;
}else if (msg1.tp == 1 && msg1.num == 0){
msg3 = Msg2(1, len2, 0, 0, 0);
if (msg2.tp <= 1){
if (msg2.num > 0) return -flg;
}else{
int pos = T.askl1(rt[msg2.R], 1, n + lim, msg2.r);
if (msg2.r - pos < msg2.len) return -flg;
}
}else if (msg1.tp == 1 && msg1.num == 1){
msg3 = Msg2(1, len2, 1, 0, 0);
if (msg2.tp == 0){
if (msg2.num < ((1 << msg2.len) - 1)) return flg;
}else if (msg2.tp == 1){
if (msg2.num == 0) return flg;
}else{
int pos = T.askl0(rt[msg2.R], 1, n + lim, msg2.r);
if (msg2.r - pos < msg2.len) return flg;
}
}else{
msg3 = Msg2(2, len2, 0, msg1.R, msg1.r - msg2.len);
if (msg2.tp == 0){
int num2 = T.ask(rt[msg1.R], 1, n + lim, msg1.r - msg2.len + 1, msg1.r).a1;
if (num2 != msg2.num) return cmp(num2, msg2.num) * flg;
}else if (msg2.tp == 1){
if (msg2.num == 0){
int pos = T.askl1(rt[msg1.R], 1, n + lim, msg1.r);
if (msg1.r - pos < msg2.len) return flg;
}else{
int pos = T.askl0(rt[msg1.R], 1, n + lim, msg1.r);
if (msg1.r - pos < msg2.len) return -flg;
}
}
}
if (len2){
if (flg == -1) vec2.push_back(msg3);
else vec1.push_back(msg3);
}
}
}
return 0;
}
}
int cmp_seg(int l1, int r1, int l2, int r2, int k1, int k2){//left << k1 right << k2
int k = k2 - k1;
if (k >= 0) return cmp_seg(l1, r1, l2, r2, k);
else return -cmp_seg(l2, r2, l1, r1, -k);
}
struct Msg3{
int l, r, k;//放大
Msg3(){}
Msg3(int l, int r, int k) : l(l), r(r), k(k) {}
friend bool operator < (const Msg3 &a, const Msg3 &b){
int res = cmp_seg(a.l, a.r, b.l, b.r, a.k, b.k);
if (res == 0) return make_pair(a.l, a.r) < make_pair(b.l, b.r);
else return res == -1;
}
};
int f[N][lim + 5];
struct tree2{
#define mid ((l + r) >> 1)
#define ls (now << 1)
#define rs (now << 1 | 1)
int a[N << 2];
void build(int now, int l, int r){
a[now] = inf;
if (l == r) return;
build(ls, l, mid);
build(rs, mid + 1, r);
}
void add(int now, int l, int r, int s, int k){
if (l == r){
a[now] = k;
return;
}
if (s <= mid) add(ls, l, mid, s, k);
else add(rs, mid + 1, r, s, k);
a[now] = min(a[ls], a[rs]);
}
int ask(int now, int l, int r, int s, int t){
if (s <= l && r <= t)
return a[now];
int res = inf;
if (s <= mid) res = min(ask(ls, l, mid, s, t), res);
if (t > mid) res = min(ask(rs, mid + 1, r, s, t), res);
return res;
}
#undef mid
#undef ls
#undef rs
}T2;
bool check(Msg3 curans){
T2.build(1, 0, n);
for (int i = 1; i <= n; i++){
int rr = i - 1;
for (int j = 0; j < lim && i + j <= n; j++)
if (cmp_seg(i, i, curans.l, curans.r, n - (i + j), curans.k) <= 0){
int l = 0, r = rr, mid;
while (l <= r){
mid = (l + r) >> 1;
if (cmp_seg(mid + 1, i, curans.l, curans.r, n - (i + j), curans.k) <= 0) r = mid - 1;
else l = mid + 1;
}
f[i][j] = j ? f[i][j - 1] : inf;
if (l < i - lim) f[i][j] = min(T2.ask(1, 0, n, l, i - lim - 1) + i + j - 1, f[i][j]);
for (int k = max(i - lim, l); k < i; k++) f[i][j] = min(f[k][min(lim - 1, j + (i - k - 1))] + i - k - 1 + j, f[i][j]);
rr = l;
}else f[i][j] = inf;
T2.add(1, 0, n, i, f[i][lim - 1] - i);
}
return f[n][0] <= K;
}
void solve(){
cin >> n >> K;
T.tot = 0;
for (int i = 0; i <= n + lim; i++) cur[i] = 0;
T.build(rt[0], 1, n + lim);
for (int i = 1; i <= n; i++){
rt[i] = rt[i - 1];
cin >> a[i];
int c = 0;
prehigh[i] = prehigh[i - 1];
for (int j = 0; j < lim; j++){
c = c + ((a[i] >> j) & 1) + cur[i + j];
if (cur[i + j] != c % 2) T.add(rt[i], rt[i], 1, n + lim, i + j, c % 2);
cur[i + j] = c % 2;
if (c) prehigh[i] = max(i + j, prehigh[i]);
c /= 2;
}
pre[i] = i;
sum[i] = sum[i - 1] / 2 + a[i];
pre2[i] = (pre2[i - 1] + a[i - 1]) / 2;
}
sort(pre + 1, pre + 1 + n, [&](int i, int j){return cmp_pre(i, j) == -1;});
for (int i = 1; i <= n; i++) id[pre[i]] = i;
log2n = log2(n);
for (int i = 1; i < n; i++) st[i][0] = lcp(pre[i], pre[i + 1]);
for (int j = 1; j <= log2n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
Msg3 Ml(1, 1, 0), Mr(1, n, n - 1), Mmid, ans;
for (int i = 2; i <= n; i++)
if (Msg3(i, i, 0) < Ml)
Ml = Msg3(i, i, 0);
while (1){
vector<array<int, 4>> vec;
for (int i = 1; i <= n; i++){
int l = i + 1, r = i;
for (int j = 0; i + j <= n && j < lim; j++){
if (cmp_seg(Ml.l, Ml.r, r, i, Ml.k, n - (i + j)) != -1){
int l2 = 1, r2 = r - 1, mid;
while (l2 <= r2){
mid = (l2 + r2) >> 1;
if (cmp_seg(Ml.l, Ml.r, mid, i, Ml.k, n - (i + j)) == -1) l2 = mid + 1;
else r2 = mid - 1;
}
r = r2;
}
if (l > 1 && cmp_seg(l - 1, i, Mr.l, Mr.r, n - (i + j), Mr.k) == -1){
int l2 = 1, r2 = l - 1, mid;
while (l2 <= r2){
mid = (l2 + r2) >> 1;
if (cmp_seg(mid, i, Mr.l, Mr.r, n - (i + j), Mr.k) == -1) r2 = mid - 1;
else l2 = mid + 1;
}
l = l2;
}
if (l <= r) vec.push_back({i, n - (i + j), l, r});
}
}
long long sz = 0;
for (auto [r, k, l1, l2] : vec) sz += l2 - l1 + 1;
if (sz == 0) break;
long long mid = (rnd() | ((1ll * rnd()) << 31)) % sz;
for (auto [r, k, l1, l2] : vec)
if (mid >= l2 - l1 + 1) mid -= l2 - l1 + 1;
else{
Mmid = Msg3(l1 + mid, r, k);
break;
}
if (check(Mmid)) Mr = Mmid;
else Ml = Mmid;
}
ans = check(Ml) ? Ml : Mr;
for (int i = 1; i <= n + lim; i++) cur[i] = 0;
for (int i = ans.l; i <= ans.r; i++){
int c = 0;
for (int j = 0; j < lim; j++){
c = c + ((a[i] >> j) & 1) + cur[i + j + ans.k];
cur[i + j + ans.k] = c % 2;
c /= 2;
}
}
int i = n + lim;
while (cur[i] == 0) i--;
for (; i >= 0; i--) cout << cur[i];
cout << endl;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
all1[1] = Msg(1, 1, 1);
for (int i = 2; i < N; i++) all1[i] = all1[i - 1] + all1[1];
pw1[0] = pw2[0] = 1;
pw[0] = 1;
for (int i = 1; i < N * 2; i++){
pw1[i] = 2ll * pw1[i - 1] % mod1;
pw2[i] = 2ll * pw2[i - 1] % mod2;
pw[i] = pw[i - 1] / 2;
}
cin >> tt;
while (tt--) solve();
return 0;
}
詳細信息
answer.code:123:22: error: ISO C++ forbids declaration of ‘cmp’ with no type [-fpermissive]
123 | template<typename T> cmp(T a, T b){
| ^~~
answer.code: In function ‘int cmp_seg(int, int, int, int, int)’:
answer.code:160:22: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
160 | auto [vec1, ph1] = getMsg(l1, r1);
| ^
answer.code:161:22: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
161 | auto [vec2, ph2] = getMsg(l2, r2);
| ^
answer.code: In function ‘void solve()’:
answer.code:360:27: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
360 | for (auto [r, k, l1, l2] : vec) sz += l2 - l1 + 1;
| ^
answer.code:363:27: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
363 | for (auto [r, k, l1, l2] : vec)
| ^