QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#505725 | #4682. Pipe Stream | Max_s_xaM | AC ✓ | 23ms | 3720kb | C++14 | 4.5kb | 2024-08-05 10:06:34 | 2024-08-05 10:06:34 |
Judging History
answer
#include <iostream>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 1e3 + 10;
int t;
lf cm, bnd[MAXN];
ll bg[MAXN], pw[MAXN];
inline bool Calc(int n, lf v1, lf v2)
{
// cout << "Calc " << n << ' ' << v1 << ' ' << v2 << "\n";
for (int i = 1; i <= n; i++) bnd[i] = cm / i, bg[i] = pw[i] = 0;
while (n && bnd[n] < v1) n--;
for (int i = n; i >= 1 && n - i <= 32; i--) bg[i] = (1ll << n - i), pw[i] = bg[i] << 1;
// for (int i = 1; i <= n; i++) cout << bg[i] << ' ' << pw[i] << ' ' << bnd[i] << '\n';
ll ad = 0, cur;
while (n)
{
ll mn = 1e18; int p = 0;
for (int i = n; i >= 1 && n - i <= 32; i--)
{
if ((bg[i] + ad) * t + v1 > bnd[i]) cur = 0;
else cur = (ll)(((bnd[i] - v1) / t - bg[i] - ad) / pw[i]) + 1;
if (mn > bg[i] + ad + cur * pw[i]) mn = bg[i] + ad + cur * pw[i], p = i;
}
// cout << mn << ' ' << p << " " << v1 << " " << (1ll << n) << " " << ad << "\n";
if (n <= 32 && mn >= (1ll << n) + ad) return ((1ll << n) + ad) * t + v1 >= v2;
if ((mn - 1) * t + v1 >= v2 - t) return 1;
ll cnt = 0;
if (bnd[p] > (mn - 1) * t + v1)
{
v1 = bnd[p] - mn * t;
if (bnd[p] >= v2 - t) return 1;
}
else cnt--;
if (p == 1) break;
for (int i = p; i <= n; i++)
cnt += (mn - ad - (pw[i] >> 1)) / pw[i] + 1;
mn -= ad, ad += cnt;
for (int i = p - 1; i >= 1 && p - 1 - i <= 32; i--)
{
if (!bg[i]) { bg[i] = (1ll << p - 1 - i); continue; }
ll c = mn + (pw[i + 1] >> 1);
if (__builtin_ctzll(c) == n - i) bg[i] = c >> n - p + 1, mn = c;
else bg[i] = ((mn -= (pw[i + 1] >> 1)) >> n - p + 1) + (1ll << p - i);
}
n = p - 1;
for (int i = n; i >= 1 && n - i <= 32; i--)
pw[i] = 1ll << n - i + 1;
// for (int i = 1; i <= n; i++) cout << bg[i] << ' '; cout << '\n';
}
return 0;
}
inline void Solve(int v1, int v2)
{
if (v2 - v1 <= t) return cout << "0\n", void();
int l = 1, r = 200, mid;
while (l <= r)
{
mid = l + r >> 1;
if (Calc(mid, v1, v2)) r = mid - 1;
else l = mid + 1;
}
if (l == 201) cout << "impossible\n";
else cout << r + 1 << '\n';
// cout << Calc(24, v1, v2) << "\n";
}
int main()
{
// freopen("G.in", "r", stdin);
// freopen("G.out", "w", stdout);
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
int T;
Read(T);
while (T--)
{
int lb, rb, l, s;
Read(l), Read(lb), Read(rb), Read(t), Read(s);
cm = l / s;
Solve(lb, rb);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
input:
3 1000 1 30 1 1 60 2 10 2 5 59 2 10 2 5
output:
5 3 impossible
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 4ms
memory: 3668kb
input:
100 1 1 2 1 1 1 1 3 1 1 2 1 3 1 1 3 1 4 1 1 4 1 4 1 1 100000 1 1000000 1 1 100000 1 9 1 1 100000 1 9454 1 1 100000 1 9455 1 1 500832 1 40181 1 1 500832 1 40182 1 1 524288 1 41871 1 1 524288 1 41872 1 1 930168 1 70677 1 1 930168 1 70678 1 1 930169 1 70677 1 1 930169 1 70678 1 1 930170 1 70677 1 1 930...
output:
0 impossible 1 impossible 2 impossible 3 24 impossible 45 impossible 32 impossible 46 impossible 46 impossible 46 impossible 45 impossible 45 impossible impossible 3 3 4 impossible 0 0 impossible 17 15 16 2 2 15 15 14 1 1 0 0 impossible 16 impossible 0 1 2 2 28 29 impossible 29 impossible 0 1 imposs...
result:
ok 100 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
40 1000 1 30 1 1 60 2 10 2 5 59 2 10 2 5 1000000 1 80235 2 1 1000000 1 80236 2 1 1000000 1 80237 2 1 1000000 1 80238 2 1 1000000 1 80239 2 1 1000000 1 80240 2 1 1000000 1 80241 2 1 1000000 1 80242 2 1 1000000 1 80243 2 1 1000000 1 75361 1 1 1000000 1 75362 1 1 1000000 1 75363 1 1 1000000 1 75364 1 1...
output:
5 3 impossible 25 25 25 26 26 26 27 29 impossible 26 26 26 27 27 28 29 impossible impossible 28 impossible 2 1 impossible 0 0 25 impossible 25 24 24 23 23 22 20 20 impossible impossible
result:
ok 40 lines
Test #4:
score: 0
Accepted
time: 8ms
memory: 3572kb
input:
100 1000000000 1 45722915 1 1 999999989 1 45722915 1 1 999999983 1 45722915 1 1 999999864 1 45722910 1 1 999995586 1 45722723 1 1 999994891 1 45722693 1 1 999992374 1 45722583 1 1 999949022 1 45720692 1 1 999905219 1 45718781 1 1 999479879 1 45700225 1 1 997558485 1 45616403 1 1 997195352 1 45600561...
output:
46 48 49 53 54 55 58 59 61 64 65 66 67 68 69 70 72 74 impossible impossible 46 47 59 55 54 56 45 53 48 43 55 44 58 42 55 45 53 49 56 52 49 54 45 43 46 43 55 47 45 50 51 62 43 50 44 46 56 55 42 47 44 53 43 5 9 4 6 11 8 10 7 39 5 23 36 12 40 impossible impossible impossible impossible impossible impos...
result:
ok 100 lines
Test #5:
score: 0
Accepted
time: 5ms
memory: 3664kb
input:
100 963597804 8589788 23029396 1 2 904990630 9613515 41508466 1 1 962305849 13680471 44078122 1 1 903367500 7401118 23692652 4 2 929904996 512484 24661207 5 2 986386365 13971769 50830247 7 1 948763065 15891434 43487320 1 1 900962516 529708 43200515 2 1 996841031 2449147 48624000 3 1 979188757 101652...
output:
40 30 36 36 36 36 36 36 41 32 37 37 29 35 29 34 32 42 25 41 41 40 37 45 46 36 26 41 36 37 40 33 39 38 29 29 37 37 38 31 30 31 36 29 35 29 34 29 38 26 34 38 36 31 36 37 41 40 41 29 31 41 30 30 31 44 26 35 29 33 36 36 32 32 36 34 47 44 34 31 38 36 35 37 44 26 31 36 30 31 43 29 35 37 37 36 30 36 43 29
result:
ok 100 lines
Test #6:
score: 0
Accepted
time: 23ms
memory: 3660kb
input:
100 1000000000 1 1000000000 1 1 1000000000 1 1000000000 1 1 1000000000 1 1000000000 1 1 1000000000 1 1000000000 1 1 1000000000 1 1000000000 1 1 1000000000 1 1000000000 1 1 1000000000 1 1000000000 1 1 1000000000 1 1000000000 1 1 1000000000 1 1000000000 1 1 1000000000 1 1000000000 1 1 1000000000 1 100...
output:
impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible imp...
result:
ok 100 lines
Test #7:
score: 0
Accepted
time: 5ms
memory: 3720kb
input:
100 1000000000 1 45722915 1 1 1000000000 1 45722915 1 1 1000000000 1 45722915 1 1 1000000000 1 45722915 1 1 1000000000 1 45722915 1 1 1000000000 1 45722915 1 1 1000000000 1 45722915 1 1 1000000000 1 45722915 1 1 1000000000 1 45722915 1 1 1000000000 1 45722915 1 1 1000000000 1 45722915 1 1 1000000000...
output:
46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46
result:
ok 100 lines
Test #8:
score: 0
Accepted
time: 7ms
memory: 3592kb
input:
100 997195352 1 45600561 1 1 995611190 1 45531451 1 1 990196526 1 45295232 1 1 984748288 1 45057548 1 1 983719132 1 45012651 1 1 978427516 1 44781800 1 1 976791672 1 44710435 1 1 976243240 1 44686509 1 1 965941755 1 44237099 1 1 955034506 1 43761262 1 1 952120032 1 43634116 1 1 950463125 1 43561832 ...
output:
66 67 66 66 68 67 67 67 66 66 66 66 69 69 66 66 66 66 67 66 67 66 68 66 68 70 66 72 66 66 68 66 67 66 66 67 66 67 66 68 66 68 66 66 70 68 66 66 66 67 66 66 71 66 66 66 67 71 66 68 68 66 67 66 67 66 66 66 66 69 66 69 66 66 68 67 69 67 66 67 68 66 67 66 67 66 66 66 72 69 68 66 66 66 66 66 66 66 74 66
result:
ok 100 lines
Test #9:
score: 0
Accepted
time: 8ms
memory: 3648kb
input:
100 672406399 1 31431395 1 1 672406399 1 31431395 1 1 672406399 1 31431395 1 1 672406399 1 31431395 1 1 672406399 1 31431395 1 1 672406399 1 31431395 1 1 672406399 1 31431395 1 1 672406399 1 31431395 1 1 672406399 1 31431395 1 1 672406399 1 31431395 1 1 672406399 1 31431395 1 1 672406399 1 31431395 ...
output:
74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74
result:
ok 100 lines