QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#858011 | #147. Floppy | binminh01 | 0 | 40ms | 9188kb | C++20 | 9.4kb | 2025-01-16 12:16:43 | 2025-01-16 12:16:43 |
Judging History
floppy
#include<bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define double long double
#define gcd __gcd
#define lcm(a, b) ((a)/gcd(a, b)*(b))
#define sqrt sqrtl
#define log2 log2l
#define log10 log10l
#define floor floorl
#define to_string str
#define yes cout << "YES"
#define no cout << "NO"
#define trav(i, a) for (auto &i: (a))
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (int)a.size()
#define Max(a) *max_element(all(a))
#define Min(a) *min_element(all(a))
#define Find(a, n) (find(all(a), n) - a.begin())
#define Count(a, n) count(all(a), n)
#define Upper(a, n) (upper_bound(all(a), n) - a.begin())
#define Lower(a, n) (lower_bound(all(a), n) - a.begin())
#define next_perm(a) next_permutation(all(a))
#define prev_perm(a) prev_permutation(all(a))
#define sorted(a) is_sorted(all(a))
#define sum(a) accumulate(all(a), 0)
#define sumll(a) accumulate(all(a), 0ll)
#define Sort(a) sort(all(a))
#define Reverse(a) reverse(all(a))
#define Unique(a) Sort(a), (a).resize(unique(all(a)) - a.begin())
#define pb push_back
#define eb emplace_back
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define clz __builtin_clz
#define clzll __buitlin_clzll
#define ctz __builtin_ctz
#define ctzll __builtin_ctzll
#define open(s) freopen(s, "r", stdin)
#define write(s) freopen(s, "w", stdout)
#define fileopen(s) open((string(s) + ".inp").c_str()), write((string(s) + ".out").c_str());
#define For(i, a, b) for (auto i = (a); i < (b); ++i)
#define Fore(i, a, b) for (auto i = (a); i >= (b); --i)
#define FOR(i, a, b) for (auto i = (a); i <= (b); ++i)
#define ret(s) return void(cout << s);
constexpr int mod = 1e9 + 7, mod2 = 998244353;
constexpr double eps = 1e-9;
const double PI = acos(-1);
constexpr ull npos = string::npos;
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using cd = complex<double>;
mt19937 mt(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 mt64(chrono::system_clock::now().time_since_epoch().count());
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<double> vdo;
typedef vector<vdo> vvdo;
typedef vector<string> vs;
typedef vector<pii> vpair;
typedef vector<vpair> vvpair;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<cd> vcd;
typedef priority_queue<int> pq;
typedef priority_queue<int, vi, greater<int>> pqg;
typedef priority_queue<ll> pqll;
typedef priority_queue<ll, vll, greater<ll>> pqgll;
ll add(ll a, ll b, int m) {a = (a >= m ? a % m: a);b = (b >= m ? b % m: b);a+=b;return a >= m ? a - m: a;}
ll sub(ll a, ll b, int m) {a = (a >= m ? a % m: a);b = (b >= m ? b % m: b);a-=b;return a < 0 ? a + m: a;}
ll mul(ll a, ll b, int m) {a = (a >= m ? a % m: a);b = (b >= m ? b % m: b);return a*b % m;}
ll bin_mul(ll a, ll b, ll m) {a = (a >= m ? a % m: a);b = (b >= m ? b % m: b);ll x = 0;while (b) {if (b & 1) x = (x + a) % m;a = (a + a) % m;b>>=1;}return x;}
ll bin_pow(ll a, ll b, ll m) {ll x = 1;a = (a >= m ? a % m: a); while (b) {if (b & 1) x = bin_mul(x, a, m);a = bin_mul(a, a, m);b>>=1;}return x;}
ll power(ll a, ll b, int m) {ll x = 1;a = (a >= m ? a % m: a); while (b) {if (b & 1) x = x*a % m;a = a*a % m;b>>=1;}return x;}
ll power(ll a, ll b) {ll x = 1;while (b) {if (b & 1) x = x*a;a = a*a;b>>=1;}return x;}
ll ceil(ll a, ll b) {return (a + b - 1)/b;}
ll to_int(const string &s) {ll x = 0; for (int i = (s[0] == '-'); i < sz(s); ++i) x = x*10 + s[i] - '0';return x*(s[0] == '-' ? -1: 1);}
bool is_prime(ll n) {if (n < 2) return 0;if (n < 4) return 1;if (n % 2 == 0 || n % 3 == 0) return 0;for (ll i = 5; i*i <= n; i+=6) {if(n % i == 0 || n % (i + 2) == 0) return 0;}return 1;}
bool is_square(ll n) {ll k = sqrt(n); return k*k == n;}
ll factorial(int n) {ll x = 1;for (int i = 2; i <= n; ++i) x*=i;return x;}
ll factorial(int n, int m) {ll x = 1;for (ll i = 2; i <= n; ++i) x = x*i % m;return x;}
bool is_power(ll n, ll k) {while (n % k == 0) n/=k;return n == 1ll;}
string str(ll n) {if (n == 0) return "0"; string s = ""; bool c = 0; if (n < 0) c = 1, n = -n; while (n) {s+=n % 10 + '0'; n/=10;} if (c) s+='-'; Reverse(s); return s;}
string repeat(const string &s, int n) {if (n < 0) return ""; string x = ""; while (n--) x+=s; return x;}
string bin(ll n) {string s = ""; while (n) {s+=(n & 1) + '0'; n>>=1;} Reverse(s); return s;}
void sieve(vector<bool> &a) {int n = a.size(); a[0] = a[1] = 0; for (int i = 4; i < n; i+=2) a[i] = 0; for (int i = 3; i*i < n; i+=2) {if (a[i]) {for (int j = i*i; j < n; j+=(i << 1)) a[j] = 0;}}}
void sieve(bool a[], int n) {a[0] = a[1] = 0; for (int i = 4; i < n; i+=2) a[i] = 0; for (int i = 3; i*i < n; i+=2) {if (a[i]) {for (int j = i*i; j < n; j+=(i << 1)) a[j] = 0;}}}
void sieve(vector<int> &a) {int n = a.size(); for (int i = 2; i < n; i+=2) a[i] = 2; for (int i = 3; i*i < n; i+=2) {if (!a[i]) {for (int j = i; j < n; j+=(i << 1)) a[j] = i;}} for (int i = 3; i < n; i+=2) {if (!a[i]) a[i] = i;}}
void sieve(int a[], int n) {for (int i = 2; i < n; i+=2) a[i] = 2; for (int i = 3; i*i < n; i+=2) {if (!a[i]) {for (int j = i; j < n; j+=(i << 1)) a[j] = i;}} for (int i = 3; i < n; i+=2) {if (!a[i]) a[i] = i;}}
vector<pii> factorize(int n) {vector<pii> a; for (int i = 2; i*i <= n; ++i) {if (n % i == 0) {int k = 0; while (n % i == 0) ++k, n/=i; a.emplace_back(i, k);}} if (n > 1) a.emplace_back(n, 1); return a;}
int rand(int l, int r) {return uniform_int_distribution<int>(l, r)(mt);}
ll rand(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(mt64);}
int Log2(int n) {return 31 - __builtin_clz(n);}
ll Log2(ll n) {return 63 - __builtin_clzll(n);}
template<class T> void compress(vector<T> &a) {vector<T> b; for (T &i: a) b.push_back(i); sort(all(b)); b.resize(unique(all(b)) - b.begin()); for (T &i: a) i = lower_bound(all(b), i) - b.begin();}
template<class A, class B> bool ckmin(A &a, const B &b) {return a > b ? a = b, 1: 0;}
template<class A, class B> bool ckmax(A &a, const B &b) {return a < b ? a = b, 1: 0;}
template<class A, class B> istream& operator>>(istream& in, pair<A, B> &p) {in >> p.first >> p.second; return in;}
template<class A, class B> ostream& operator<<(ostream& out, const pair<A, B> &p) {out << p.first << ' ' << p.second; return out;}
template<class T> istream& operator>>(istream& in, vector<T> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const vector<T> &a) {for (auto &i: a) out << i << ' '; return out;}
template<class T> istream& operator>>(istream& in, vector<vector<T>> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const vector<vector<T>> &a) {for (auto &i: a) out << i << '\n'; return out;}
template<class T> istream& operator>>(istream& in, deque<T> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const deque<T> &a) {for (auto &i: a) out << i << ' '; return out;}
// istream& operator>>(istream& in, __int128_t &a) {string s; in >> s; a = 0; for (auto &i: s) a = a*10 + (i - '0'); return in;}
// ostream& operator<<(ostream& out, __int128_t a) {string s = ""; if (a < 0) s+='-', a = -a; if (a == 0) s+='0'; while (a > 0) {s+=(int)(a % 10) + '0'; a/=10;} Reverse(s); out << s; return out;}
#include "floppy.h"
void read_array(int subtask_id, const vi &a) {
int n = sz(a);
vector<vpair> s(16, vpair(n));
For(i,0,n) s[0][i] = {a[i], i};
For(i,1,16) {
FOR(j,0,n-(1<<i)) s[i][j] = max(s[i - 1][j], s[i - 1][j + (1 << (i - 1))]);
}
auto get = [&](int l, int r) {
int i = __lg(r - l + 1);
return max(s[i][l], s[i][r - (1 << i) + 1]).second;
};
string t;
auto dfs = [&](auto &&dfs, int l, int r)->void{
int i = get(l, r);
t+='0' + (l < i); t+='0' + (i < r);
if (l < i) dfs(dfs, l, i - 1);
if (i < r) dfs(dfs, i + 1, r);
};
dfs(dfs, 0, n - 1);
save_to_floppy(t);
}
vi solve_queries(int subtask_id, int n, const string &t, const vi &a, const vi &b) {
vvi p(16, vi(n)), g(n);
vi h(n);
int k = 0, x = 0;
auto dfs = [&](auto &&dfs, int i)->pii{
//{size, vertex}
k+=2;
int u = 0, w = 1;
if (t[i] == '0') u = x;
else {
auto [s, v] = dfs(dfs, i + 2);
w+=s;
u = x;
p[0][v] = u; g[u].pb(v);
}
++x;
if (t[i + 1] == '1') {
auto [s, v] = dfs(dfs, k);
w+=s;
p[0][v] = u; g[u].pb(v);
}
return {w, u};
};
dfs(dfs, 0);
auto high = [&](auto &&high, int u)->void{
trav(v,g[u]) h[v] = h[u] + 1, high(high, v);
};
high(high, 0);
For(i,1,16) For(j,0,n) p[i][j] = p[i - 1][p[i - 1][j]];
auto lca = [&](int u, int v)->int{
if (h[u] < h[v]) swap(u, v);
int d = h[u] - h[v];
Fore(i,15,0) if (d >> i & 1) u = p[i][u];
if (u == v) return u;
Fore(i,15,0){
if (p[i][u] != p[i][v]) u = p[i][u], v = p[i][v];
}
return p[0][u];
};
vi c(sz(a));
For(i,0,sz(a)) c[i] = lca(a[i], b[i]);
return c;
}
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: 3968kb
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 11111100110010010011100011110010100000111111111111111011101110000011000010001100111000001111111011100001001101000111000001010000110110001000111111011100001100001110110001001111000001111000001111101001010000001111000011111100000010001111111101110110000111000011001111110111000101000101100011111100...
input:
1 496 992 11111100110010010011100011110010100000111111111111111011101110000011000010001100111000001111111011100001001101000111000001010000110110001000111111011100001100001110110001001111000001111000001111101001010000001111000011111100000010001111111101110110000111000011001111110111000101000101100011...
output:
18 1 115 0 18 0 0 7 0 1 7 0 18 0 18 0 18 1 305 7 18 7 18 18 305 18 18 1 1 0 0 18 0 0 1 18 115 7 1 1 1 18 115 0 18 18 18 18 18 115 18 1 1 252 0 1 7 1 1 1 18 305 1 18 18 0 0 0 18 18 18 7 18 18 1 1 7 1 18 18 0 1 0 7 18 240 18 373 18 1 7 18 18 0 0 0 18 18 1 1 7 18 18 18 18 1 7 7 0 67 18 1 18 18 476 0 1 ...
result:
wrong answer wrong answer on query #1 (a = 109, b = 205): read 18 but expected 115
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 8ms
memory: 5192kb
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 111111111111000011111111110001001110000001001111110100001100100011111111101010100100010011111101010000011111000001001100001111100000010111000100111011110000001110100011111101100000101011000100111111000011010000010011001111011000111110001111111111100100110100011001001000100110010011110010100110...
input:
2 9998 19996 11111111111100001111111111000100111000000100111111010000110010001111111110101010010001001111110101000001111100000100110000111110000001011100010011101111000000111010001111110110000010101100010011111100001101000001001100111101100011111000111111111110010011010001100100100010011001001111001...
output:
359 0 359 359 3 6131 247 6131 359 5760 1 359 1 359 3 6131 6131 3 6131 6131 6131 0 247 5760 247 6131 247 3 5760 6664 6131 6131 359 247 359 5760 1 359 5760 3 1 359 5760 359 3 359 247 1 0 5760 6131 1 359 0 247 247 6131 6131 0 6131 359 3 0 359 0 1 247 3 6131 3 3 359 359 359 0 1 359 5760 3 6131 6131 3 0 ...
result:
wrong answer wrong answer on query #1 (a = 2131, b = 6955): read 359 but expected 6131
Subtask #3:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 40ms
memory: 9188kb
input:
3 39995 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 989156210 99...
output:
79990 111111111111111110111010010011111000110011110010010011100100101101000001001011100000111111111101010100110000110011110111000010110010000011110111011010100010001100111111000000010110101000110011101111111111010010010010010011100010001111101010000011001000110110001110000101110001001000111111001111...
input:
3 39995 79990 1111111111111111101110100100111110001100111100100100111001001011010000010010111000001111111111010101001100001100111101110000101100100000111101110110101000100011001111110000000101101010001100111011111111110100100100100100111000100011111010100000110010001101100011100001011100010010001111...
output:
4 3597 39520 29 16794 7409 29 3 554 39520 29 2 29 28 3 35 4 554 29 35 554 28 28 2 4 35 39520 0 17919 37333 3 434 3 4 434 39520 554 35 39520 3 39520 35 4 29 17919 554 0 4 35 4 554 17919 17919 28 28370 2 35 35 333 2 434 17919 4 3 3597 28 333 29 4 333 584 17919 35 27076 35 35 2 554 39520 39520 2 39520 ...
result:
wrong answer wrong answer on query #1 (a = 9100, b = 12589): read 4 but expected 11215