QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#338110 | #7111. Press the Button | Lain | WA | 2ms | 3800kb | C++23 | 2.9kb | 2024-02-25 17:53:45 | 2024-02-25 17:53:45 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
const int N = 1e6+7;
int tt;
cin >> tt;
while(tt--) {
int64_t a,b,c,d,v,t;
cin >> a >> b >> c >> d >> v >> t;
v++;
int64_t ans = b*((t/a) + 1) + d*((t/c)+ 1);
struct node {
int presses = 0;
int64_t time_from_zero = 0;
bool valid = false;
};
vector<vector<node>> nodes(2, vector<node>(max(a, c) + 1, node{}));
auto get_idx = [&](int mod_a, int mod_b)->pair<int, int> {
if (mod_a == mod_b && mod_a == 0) {
return {0, 0};
} else if (mod_a == 0) {
return {1, mod_b};
} else if (mod_b == 0) {
return {0, mod_a};
} else assert(false);
return {-1, -1};
};
auto dfs = [&](auto& self, int mod_a, int mod_c, bool ignore_valid)->void {
if (t < 0) return;
auto curridx = get_idx(mod_a, mod_c);
auto currnode = nodes[curridx.first][curridx.second];
int next_mod_a = (mod_a + v)%a;
int a_diff = next_mod_a == 0?0:(a - next_mod_a);
int next_mod_c = (mod_c + v)%c;
int c_diff = next_mod_c == 0?0:(c - next_mod_c);
next_mod_a = (next_mod_a + min(a_diff, c_diff))%a;
next_mod_c = (next_mod_c + min(a_diff, c_diff))%c;
auto nextidx = get_idx(next_mod_a, next_mod_c);
if (!ignore_valid && nodes[nextidx.first][nextidx.second].valid) {
// cycle completed!
ans--; // make a press to go back to the beginning of the cycle.
// Spend the time to go to the beginning of the cycle
t -= v + min(a_diff, c_diff);
// Already made all the steps necessary.
if (t < 0) return;
auto& nxtnode = nodes[nextidx.first][nextidx.second];
int64_t total_cycle_time = currnode.time_from_zero - nxtnode.time_from_zero + v + min(a_diff, c_diff);
int64_t total_cycle_presses = currnode.presses - nxtnode.presses + 1;
int64_t num_cycles = t / total_cycle_time;
t %= total_cycle_time;
ans -= num_cycles * total_cycle_presses;
self(self, next_mod_a, next_mod_c, true);
return;
} else {
auto& nxtnode = nodes[nextidx.first][nextidx.second];
// Make a press
ans--;
// Spend the time to go to the next step;
t -= v + min(a_diff, c_diff);
// Calculate the values of the next node.
nxtnode.valid = true;
nxtnode.presses = currnode.presses + 1;
nxtnode.time_from_zero = currnode.time_from_zero + v + min(a_diff, c_diff);
self(self, next_mod_a, next_mod_c, ignore_valid);
}
};
nodes[0][0] = node{1, 0, true};
dfs(dfs, 0, 0, false);
cout << ans << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
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: -100
Wrong Answer
time: 2ms
memory: 3716kb
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:
67 201 52 16 35 22 7 102 30 496 57 75 96 52 84 43 147 80 20 174 41 3 457 135 54 30 45 124 201 117 40 63 36 94 61 117 24 135 17 73 24 170 114 39 31 11 29 81 33 7 66 46 483 47 47 14 13 52 421 153 90 27 20 132 69 88 33 280 56 294 18 86 151 52 8 216 201 381 27 49 61 210 26 18 26 19 123 100 113 54 44 15 ...
result:
wrong answer 1st numbers differ - expected: '71', found: '67'