QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#218598 | #7111. Press the Button | ucup-team992 | AC ✓ | 3ms | 8404kb | C++17 | 3.6kb | 2023-10-18 15:35:25 | 2023-10-18 15:35:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define ll long long
typedef int uci;
#define int long long
#define F first
#define S second
typedef complex<double> cd;
seed_seq seq{
(uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
(uint64_t) __builtin_ia32_rdtsc(),
(uint64_t) (uintptr_t) make_unique<char>().get()
};
mt19937 rng(seq);
// mt19937_64 lrng(seq);
struct debugger{
template <typename T>
debugger& operator<<(T &a){
#ifdef DEBUG
cerr << a;
#endif
return *this;
}
template <typename T>
debugger& operator<<(T &&a){
#ifdef DEBUG
cerr << a;
#endif
return *this;
}
} deb;
const double PI = acos(-1.0);
const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
//! function insert
//THINK FIRST, CODE SECOND
//DON'T GET STUCK ON ONE STRATEGY
//CALM DOWNNN FOR ONCE IN YOUR LIFE
//REDUCE
//COUGH E??!?!?!! O.O
//uwu i see you ryan
int mods[1000001];
int mult[1000001];
void solve() {
int a, b, c, d, v, t;
cin >> a >> b >> c >> d >> v >> t;
// 100 test cases per file
// repeats with cycle of length lcm(a, c)
// maybe, just the number of presses - number of groups
int total = (t/a + 1) * b + (t/c + 1)*d;
// now need to determine number of groups of presses
// for one of the elements, we find the moduli
if(v >= min(a, c)){
cout << total-1 << '\n';
return;
}
total -= (t/a+1) + (t/c+1);
int ind{};
mods[ind] = 0;
mult[ind++] = 0;
int count{};
if(a < c){
swap(a, c);
swap(b, d);
}
int amt = c;
count += amt/a;
amt %= a;
while(amt != 0){
mods[ind] = amt;
mult[ind++] = count;
amt += c;
count += amt/a;
amt %= a;
}
// cycles in (count*a)
int cyc = count*a;
for(int i{}; i < ind; ++i){
// cout << mult[i]*a+mods[i] << ' '<< total << '\n';
if(mods[i] <= v && t-mult[i]*a-mods[i] >= 0){
total += ((t-mult[i]*a-mods[i])/cyc + 1);
}
if(a-mods[i] <= v && t-mult[i]*a-a >= 0){
total += ((t-mult[i]*a-a)/cyc + 1);
}
// cout << mult[i]*a+mods[i] << ' '<< total << '\n';
}
cout << total << '\n';
}
uci main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
// cout << "Case #" << t << ": ";
solve();
}
}
/*
random number generator stuff
num = rng(); gives integer number
num = uniform_int_distribution<int>(a, b)(rng); -> bounds [a, b]
num = uniform_real_distribution<double>(a, b)(rng); -> bounds [a, b)
can also instantiate distributions and call on generator:
uniform_int_distribution<int> thing(a, b);
num = thing(rng);
*/
// struct custom_hash {
// static uint64_t splitmix64(uint64_t x) {
// // http://xorshift.di.unimi.it/splitmix64.c
// x += 0x9e3779b97f4a7c15;
// x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
// x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
// return x ^ (x >> 31);
// }
// size_t operator()(uint64_t x) const {
// static const uint64_t FIXED_RANDOM = lrng();
// return splitmix64(x + FIXED_RANDOM);
// }
// };
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5836kb
input:
2 8 2 5 1 2 18 10 2 5 1 2 10
output:
6 4
result:
ok 2 number(s): "6 4"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5620kb
input:
1000 8 6 2 6 3 17 1 6 1 1 1 30 5 4 8 8 1 31 7 6 10 3 6 12 9 1 4 4 3 38 3 3 5 8 1 8 9 1 5 2 3 18 6 10 10 8 2 40 9 6 9 10 3 9 2 5 1 10 10 39 7 7 1 2 4 19 8 10 8 6 7 36 2 9 1 1 7 17 1 2 3 5 6 14 8 8 8 7 1 46 6 9 3 9 4 6 10 8 1 7 10 18 7 1 7 10 3 50 1 10 2 1 5 1 5 8 4 9 7 44 9 2 5 4 7 42 9 1 2 1 1 20 5 ...
output:
71 216 52 16 38 22 7 102 30 499 60 75 98 54 84 44 148 80 20 179 45 4 463 139 56 30 45 127 204 121 42 69 38 98 63 121 25 142 17 75 24 175 114 40 32 11 29 85 35 7 66 49 492 49 49 14 17 53 431 161 94 27 21 135 71 92 33 290 57 300 18 89 155 55 10 219 203 390 28 50 67 213 26 18 27 19 128 101 118 62 46 15...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 8404kb
input:
100 9 9 3 1 1 2 5 5 7 7 7 50 2 1 8 10 10 45 3 4 5 7 7 38 1 6 9 5 2 13 5 6 7 9 1 29 10 1 4 3 3 19 6 10 10 8 7 3 9 3 10 3 3 14 9 7 1 7 8 38 3 78 5 43 5 958 4 98 3 42 10 7 3 16 9 71 7 52 1 70 3 86 3 410 10 44 1 56 3 628 9 15 9 94 10 15 9 95 9 61 2 525 2 23 8 37 10 108 5 92 3 65 10 331 6 54 6 44 3 537 2...
output:
9 110 82 107 93 73 13 17 10 307 33215 321 713 40551 37995 217 9145 1782 13378 8730 270 2433 143 17 30 136 10 82 33 97 733 126 2917 623 364 1448 1212 872 268 1031 1601 3889 122 523 819 83 17513 277 2973 4651 202187 42602 17225 7881 32574 7087 4453 34029 20529 17520 58488 189327 14380 67133 90956 4328...
result:
ok 100 numbers
Extra Test:
score: 0
Extra Test Passed