QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #858321 | #147. Floppy | thanhs | 0 | 14ms | 10344kb | C++20 | 2.5kb | 2025-01-16 16:11:37 | 2025-01-16 16:11:37 |
Judging History
floppy
#include <bits/stdc++.h>
using namespace std;
#include "floppy.h"
#define name "TENBAI"
#define fi first
#define se second
// #define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
const int NM = 4e4 + 5;
vector<int> g[NM];
string res;
int n, dep[NM], up[NM][21];
pair<int, int> st[NM][21];
int get(int l, int r)
{
int L = __lg(r - l + 1);
return max(st[l][L], st[r - (1 << L) + 1][L]).se;
}
void dnc(int l, int r)
{
int m = get(l, r);
if (l <= m - 1)
{
res += '1';
dnc(l, m - 1);
}
else
res += '0';
if (m + 1 <= r)
{
res += '1';
dnc(m + 1, r);
}
else
res += '1';
}
void read_array(int _, const vector<int>& v)
{
n = v.size();
for (int i = 1; i <= n; i++)
st[i][0] = {v[i - 1], i};
for (int i = 1; (1 << i) <= n; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
st[j][i] = max(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);
dnc(1, n);
save_to_floppy(res);
}
int p = 0;
pair<int, int> build(int c)
{
int u = c + 1, cnt = 1;
if (res[p++] == '1')
{
auto t = build(c);
u += t.se;
g[u].push_back(t.fi);
up[t.fi][0] = u;
c += t.se;
cnt += t.se;
}
c++;
if (res[p++] == '1')
{
auto t = build(c);
g[u].push_back(t.fi);
up[t.fi][0] = u;
cnt += t.se;
}
return {u, cnt};
}
void dfs(int u)
{
for (int v : g[u])
{
dep[v] = dep[u] + 1;
dfs(v);
}
}
int lca(int u, int v)
{
if (dep[u] < dep[v])
swap(u, v);
int k = dep[u] - dep[v];
while (k)
u = up[u][__lg(k & -k)], k ^= k & -k;
for (int i = __lg(n); i >= 0; i--)
if (up[u][i] != up[v][i])
u = up[u][i], v = up[v][i];
return up[u][0];
}
vector<int> solve_queries(int _, int N, const string& bits, const vector<int>& a, const vector<int>& b)
{
n = N;
res = bits;
build(0);
for (int i = 1; (1 << i) <= n; i++)
for (int j = 1; j <= n; j++)
up[j][i] = up[up[j][i - 1]][i - 1];
vector<int> ans;
for (int i = 0; i < a.size(); i++)
ans.push_back(lca(a[i] + 1, b[i] + 1) - 1);
return ans;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 8812kb
input:
1 496 484 491 478 483 452 446 458 493 453 457 468 418 440 241 267 365 462 441 495 39 54 70 26 97 152 24 105 85 170 298 42 275 305 295 297 207 211 296 184 346 98 123 171 157 135 194 243 156 115 196 169 53 138 93 263 251 201 195 333 324 396 338 270 311 359 289 290 486 403 183 339 310 473 464 471 469 4...
output:
992 11101110111010111110111110111101111011111111111111011101111011011110111101111011101111111101110101111010110110110110101011011101101111011111101101101110110111110110101111101101101110111011111101010111101101111011011111011011011101111111011011011101101101110111110110110101011010110111111011110111...
input:
1 496 992 11101110111010111110111110111101111011111111111111011101111011011110111101111011101111111101110101111010110110110110101011011101101111011111101101101110110111110110101111101101101110111011111101010111101101111011011111011011011101111111011011011101101101110111110110110101011010110111111011...
output:
-1 -1 -1 498 -1 -1 117 117 -1 117 -1 117 -1 -1 498 498 498 498 117 117 -1 -1 498 -1 117 498 -1 674 689 -1 -1 -1 -1 117 -1 117 -1 498 689 -1 -1 117 -1 117 -1 660 -1 -1 498 -1 -1 498 498 -1 -1 -1 -1 -1 -1 117 -1 -1 -1 -1 498 498 -1 -1 -1 117 -1 -1 -1 117 117 498 -1 -1 -1 -1 498 117 117 -1 -1 245 498 1...
result:
wrong answer wrong answer on query #1 (a = 109, b = 205): read -1 but expected 115
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 14ms
memory: 10344kb
input:
2 9998 941669562 945620824 923950848 951745929 487936934 545172907 544098433 249251812 620978276 575815248 584717207 588068187 353162497 679201670 592738155 438327774 762119945 576801563 408534366 592715009 525377786 603981493 -93758897 137509462 -38676966 -36724784 654920761 -595506762 -645387884 -...
output:
19996 111111011011111110110101111011101101011111010110111011101111111111101011111101011111010101101101110110110101110110111110111011010110110101111110110110111111011111110110111011111011010111111101101110101101101011101111011011111101111111110101111010110110101111011110110101111110111101101111101110...
input:
2 9998 19996 11111101101111111011010111101110110101111101011011101110111111111110101111110101111101010110110111011011010111011011111011101101011011010111111011011011111101111111011011101111101101011111110110111010110110101110111101101111110111111111010111101011011010111101111011010111111011110110111...
output:
-1 -1 -1 -1 9999 10002 -1 14976 -1 10002 -1 10002 -1 10002 10002 -1 -1 14049 -1 9999 -1 -1 -1 10002 -1 9999 14757 -1 -1 9999 -1 10002 10002 -1 9999 9999 9999 -1 -1 -1 9999 9999 -1 9999 -1 -1 -1 -1 9999 10002 -1 -1 10002 11838 10002 13828 10002 9999 -1 -1 10002 9999 10002 9999 -1 -1 10002 9999 -1 999...
result:
wrong answer wrong answer on query #1 (a = 2131, b = 6955): read -1 but expected 6131
Subtask #3:
score: 0
Program floppy Runtime Error
Test #11:
score: 0
Program floppy Runtime Error
input:
3 39995 79990 922975946 766568552 929754744 983095922 988967630 879723897 928174186 951250463 831467029 836738151 464712826 467214506 167661408 156498284 426000721 530835328 -35115993 -86200136 327603078 448684869 192895652 125768327 402822176 196767853 409109378 985776352 976681898 967347754 989156...
output:
79990 111111111111010111111101111011110111010111110101111101011011101011111101110111111110101010111011011101111011011011110111011110111101101111011111101111011111011011011010111101111110111111111010111010111101011111011110111111110111110111011101111011011111011101011011010111101111110111101110111101...