QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#802739#9832. If I Could Turn Back Timeucup-team3723#WA 0ms3740kbC++202.6kb2024-12-07 14:33:292024-12-07 14:33:35

Judging History

This is the latest submission verdict.

  • [2024-12-07 14:33:35]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3740kb
  • [2024-12-07 14:33:29]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define ALL(v) v.begin(),v.end()
#define dbg(x) cerr << #x << ": " << (x) << endl;

mt19937 rnd;
int n;
vector<int> h,p;

void input() {
    cin >> n;
    h.resize(n);
    p.resize(n);
    for (int i = 0; i < n; ++i) cin >> h[i];
    for (int i = 0; i < n; ++i) cin >> p[i];
}

void gen() {
    n = 5;
    h.resize(n);
    p.resize(n);
    for (int i = 0; i < n; ++i) h[i] = rnd() % 10;
    // sort(ALL(h));
    for (int i = 0; i < n; ++i) p[i] = rnd() % 10 + h[i];
}

int naive() {
    int cnt = 0;
    for (int i = 0; i < n; ++i) if (p[i] < h[i]) return -1;
    while (true) {
        int idx = 1e9;
        for (int i = 0; i < n; ++i) if (p[i] > h[i]) {
            if (idx < n) {
                if (p[idx] - h[idx] < p[i] - h[i]) {
                    idx = i;
                }
            }
            else {
                idx = i;
            }
        }
        if (idx == 1e9) break;
        int mi = p[idx];
        for (int i = 0; i < n; ++i) if (p[i] >= mi) {
            if (p[i] - 1 < h[i]) {
                return -1;
            }
            p[i] -= 1;
        }
        ++cnt;
    }
    return cnt;
}

int solve() {

    vector<int> ord(n);
    iota(ALL(ord),0);
    sort(ALL(ord), [&](int i, int j) {
        return p[i] < p[j];
    });
    
    bool ok = true;
    for (int i = 0; i+1 < n; ++i) {
        int x = ord[i];
        int y = ord[i+1];
        if (p[x] == p[y]) {
            if (h[x] != h[y]) {
                ok = false;
                break;
            }
        }
        else {
            if (h[x] > h[y]) {
                ok = false;
                break;
            }
        }
    }
    if (ok) {
        for (int i = 0; i < n; ++i) if (p[i] < h[i]) {
            ok = false;
            break;
        }
    }
    int ans = -1;
    if (ok) {
        ans = p[ord.back()] - h[ord.back()];
    }

    return ans;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        input();
        cout << solve() << '\n';
    }

    // while (true) {
    //     gen();
    //     auto ch = h, cp = p;
    //     int x = solve();
    //     int y = naive();
    //     dbg(x)
    //     if (x != y) {
    //         for (int i = 0; i < n; ++i) {
    //             cerr << ch[i] << " \n"[i==n-1];
    //         }
    //         for (int i = 0; i < n; ++i) {
    //             cerr << cp[i] << " \n"[i==n-1];
    //         }
    //         dbg(x)
    //         dbg(y)
    //         break;
    //     }
    // }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3740kb

input:

4
4
3 2 4 2
5 3 6 2
1
10
100000
5
1 2 3 4 5
1 2 3 4 5
3
1 4 6
4 1 8

output:

2
99990
0
-1

result:

ok 4 number(s): "2 99990 0 -1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

10
1
1
2
2
2 7
2 7
1
6
8
1
1
1
1
3
8
2
4 4
9 7
4
5 5 5 5
8 6 6 6
2
3 3
10 3
2
6 1
8 2
4
4 6 8 9
4 7 9 10

output:

1
0
2
0
5
5
3
7
2
1

result:

ok 10 numbers

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3656kb

input:

100
1
4
9
2
57 42
67 52
2
9 53
13 68
1
5
10
1
11
41
1
4
8
1
7
16
5
1 12 66 2 14
33 21 83 11 29
1
20
22
2
29 67
59 98
4
1 12 85 1
26 16 98 5
1
4
47
5
8 8 37 40 58
11 31 54 66 89
2
22 12
75 63
1
10
10
1
34
37
7
7 16 21 62 3 16 1
9 46 55 96 4 44 2
1
4
24
4
2 1 23 18
29 28 82 68
4
73 77 66 6
80 84 72 8
...

output:

5
10
15
5
30
4
9
-1
2
31
-1
43
31
53
0
3
34
20
59
7
43
28
50
33
14
51
13
47
3
90
23
19
0
35
13
17
51
5
84
43
16
85
6
32
28
15
24
3
36
-1
45
4
13
9
10
22
-1
33
13
25
9
42
30
17
45
26
68
32
8
1
6
13
23
18
68
3
-1
59
20
20
3
55
35
4
-1
92
10
7
18
59
11
51
55
3
85
42
14
39
28
2

result:

wrong answer 13th numbers differ - expected: '-1', found: '31'