QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#338110#7111. Press the ButtonLainWA 2ms3800kbC++232.9kb2024-02-25 17:53:452024-02-25 17:53:45

Judging History

你现在查看的是最新测评结果

  • [2024-02-25 17:53:45]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3800kb
  • [2024-02-25 17:53:45]
  • 提交

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'