QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#803276#9832. If I Could Turn Back Timeucup-team3723#TL 112ms3704kbC++202.9kb2024-12-07 16:42:012024-12-07 16:42:06

Judging History

This is the latest submission verdict.

  • [2024-12-07 16:42:06]
  • Judged
  • Verdict: TL
  • Time: 112ms
  • Memory: 3704kb
  • [2024-12-07 16:42:01]
  • 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 = 20;
    h.resize(n);
    p.resize(n);
    for (int i = 0; i < n; ++i) h[i] = rnd() % 100 + 1;
    // sort(ALL(h));
    vector<int> d(n);
    for (int i = 0; i < n; ++i) d[i] = rnd() % 10;
    sort(ALL(d));
    for (int i = 0; i < n; ++i) p[i] = h[i] + d[i];
}

int naive() {
    int cnt = 0;
    for (int i = 0; i < n; ++i) if (p[i] < h[i]) return -1;

    while (true) {
        int macnt=-1, mi;
        for (int i = 0; i < n; ++i) if (p[i] > h[i]) {
            if (p[i] - h[i] > macnt) {
                macnt = p[i] - h[i];
                mi = p[i];
            }
            else if (p[i] - h[i] == macnt) {
                mi = min(mi, p[i]);
            }
        }
        if (macnt > 0) {
            for (int i = 0; i < n; ++i) if (p[i] >= mi) {
                p[i] -= 1;
            }
            ++cnt;
        }
        else {
            break;
        }
    }
    // for (int i = 0; i < n; ++i) cerr << p[i] << " \n"[i==n-1];
    for (int i = 0; i < n; ++i) if (p[i] != h[i]) {
        return -1;
    }
    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];
        int dx = p[x]-h[x];
        int dy = p[y]-h[y];
        if (dx < 0 || dy < 0) {
            ok = false;
            break;
        }

        if (p[x] == p[y]) {
            if (h[x] != h[y]) {
                ok = false;
                break;
            }
        }
        else {
            assert(p[x] < p[y]);
            if (h[x] > h[y] || dx > dy) {
                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 << naive() << '\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;
    //     }
    // }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3588kb

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: 3628kb

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: 0
Accepted
time: 1ms
memory: 3640kb

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
-1
53
0
3
34
20
59
7
-1
-1
50
33
14
51
-1
47
3
90
23
19
0
35
13
17
51
-1
84
-1
16
85
6
32
28
-1
24
3
36
-1
45
-1
13
9
10
22
-1
33
13
-1
9
42
-1
17
45
26
68
32
8
-1
6
13
23
18
68
3
-1
59
-1
20
3
55
-1
4
-1
92
10
7
18
59
11
51
55
3
-1
42
14
39
28
-1

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 3ms
memory: 3704kb

input:

1000
1
295
730
1
562
588
1
440
834
2
170 150
739 630
1
308
536
1
11
432
2
302 1
345 47
1
26
48
2
79 433
85 927
1
194
563
1
95
289
1
129
481
1
2
76
2
942 297
984 343
1
26
309
3
342 236 182
898 833 706
3
949 1 1
990 142 142
1
350
377
1
489
554
2
603 617
750 999
2
86 60
454 308
1
349
873
2
3 124
11 258...

output:

435
26
394
569
228
421
-1
22
494
369
194
352
74
-1
283
-1
-1
27
65
382
368
524
134
136
399
20
-1
317
76
-1
11
117
248
-1
747
234
39
257
-1
243
161
28
410
-1
219
402
517
0
-1
383
-1
-1
560
-1
150
283
69
-1
5
679
736
-1
178
241
6
154
250
7
152
521
-1
510
-1
253
689
152
163
455
7
-1
-1
-1
-1
127
58
138...

result:

ok 1000 numbers

Test #5:

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

input:

10000
3
1 2 3
1 2 3
3
4 2 3
2 4 3
4
1 2 2 1
1 2 2 3
4
2 3 2 3
2 2 1 1
4
1 2 3 2
2 3 3 2
3
1 1 1
4 2 1
4
3 2 1 1
2 3 3 1
4
3 1 3 3
1 3 3 2
3
4 4 1
2 3 1
4
1 2 2 3
1 2 2 2
4
3 2 3 2
2 3 1 2
3
2 1 1
3 3 1
4
2 1 1 2
1 1 1 1
4
1 3 1 3
2 1 2 2
3
1 4 2
3 1 4
3
1 2 2
1 1 1
3
4 4 4
1 3 4
4
3 3 1 3
1 3 1 1
3
...

output:

0
-1
-1
-1
-1
3
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 8ms
memory: 3644kb

input:

10000
4
3 1 3 3
3 1 3 3
3
3 1 2
3 1 3
4
1 1 2 3
2 3 3 3
4
1 1 2 1
3 1 2 2
4
1 3 2 2
3 3 3 2
4
1 1 3 2
3 1 4 2
4
1 3 2 1
3 4 2 2
3
2 2 1
3 4 4
4
1 3 3 1
2 3 4 4
4
2 2 2 4
2 2 3 4
4
1 3 3 2
1 4 4 3
4
1 2 1 3
2 3 4 3
4
1 2 2 2
3 2 2 3
4
2 3 4 3
3 3 4 4
4
1 2 4 2
3 3 4 2
3
3 1 1
4 2 4
2
2 1
3 3
4
2 4 1 ...

output:

0
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
-1
-1
-1
2
2
-1
-1
-1
-1
-1
1
-1
-1
-1
3
-1
-1
2
-1
1
-1
-1
-1
-1
1
3
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
0
-1
-1
-1
-1
1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 112ms
memory: 3636kb

input:

10000
1
1992
3361
1
2344
6367
3
2384 2669 2391
2552 9612 9008
8
2772 68 2961 3038 1455 1952 1700 1475
7154 2454 7344 7520 4697 6299 5998 4718
3
1 2377 3674
1563 6671 4111
1
835
3970
2
90 3808
905 3966
1
1884
4228
1
2230
4764
1
2666
4380
1
5235
6086
2
9014 2301
9258 2840
1
4146
9155
3
4232 131 1
6134...

output:

1369
4023
6943
4482
-1
3135
-1
2344
2534
1714
851
-1
5009
-1
2377
1
-1
2771
641
197
-1
-1
523
3784
-1
2141
16
-1
-1
-1
-1
4539
2127
931
-1
-1
7687
2636
161
1413
-1
-1
5838
3943
115
4410
4363
-1
1396
1195
1971
992
-1
1275
4611
6264
442
-1
2103
-1
4570
5051
4386
1800
5903
468
-1
-1
1384
1035
5042
2423...

result:

ok 10000 numbers

Test #8:

score: -100
Time Limit Exceeded

input:

10000
7
38298 219279 150117 108638 38514 262931 190184
49359 632891 212333 136390 49805 733473 275123
8
292669 243756 357925 275144 154345 270254 1924 152155
644616 329383 444406 539603 331796 500761 9253 171890
5
48205 121332 284583 6912 195063
483501 636162 920123 223333 768268
17
111673 400728 31...

output:

470542
-1
635540
-1
448149
-1
-1
29420
374065
-1
311800
31168
497379
-1
-1
122242
389855
684381
459586
148108
587025
-1
250271
-1
-1
-1
348760
297370
-1
336091
-1
-1
-1
102640
-1
-1
-1
292881
-1
-1
-1
472732
-1
549997
111066
-1
-1
25565
745743
444057
-1
-1
175829
610018
268482
16035
-1
447221
124317...

result: