QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#297545	#7560. Computer Network	Mag1sk	TL	1ms	7536kb	C++17	2.2kb	2024-01-04 18:27:16	2024-01-04 18:27:16

Judging History

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

[2024-01-04 18:27:16]
评测

测评结果：TL
用时：1ms
内存：7536kb

查看

[2024-01-04 18:27:16]
提交

answer

#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int N = 1e6 + 5;
const int inf = 1e9;
#define  PII pair<int,int>
int a[N], b[N];
PII c[N];
int p_a[N], p_b[N];
int tot = inf;
int n;
int now = 0;
bool flag = 0;

void dfs()
{
    //    cout<<tot<<"\n";
    if (a[1] <= b[1]) {
        int cntt = 0;
        for (int i = 2; i <= n; i++) {
            if (a[i] - a[i - 1]==p_b[i]) {
                cntt++;
            }
            else break;
        }
        if (cntt == n - 1) {
            flag = 1;
            tot = min(tot, now + b[1] - a[1]);
            return;
        }
    }
    vector<int>aa(n + 1);
    for (int i = 1; i <= n; i++) aa[i] = a[i];
    bool ok = true;
    for (int i = 2; i <= n; i++) {
        int x = a[i] / 2 - a[i - 1] / 2;
        if (x < p_b[i]) {
            ok = false;
            break;
        }
    }
    if (ok) {
        for (int i = 1; i <= n; i++) {
            a[i] /= 2;
        }
        now++;
        dfs();
        now--;
        for (int i = 1; i <= n; i++) {
            a[i] = aa[i];
        }
    }
    ok = true;
    for (int i = 2; i <= n; i++) {
        int x = (a[i] + 1) / 2 - (a[i - 1] + 1) / 2;
        if (x < p_b[i]) {
            ok = false;
            break;
        }
    }

    if (ok) {
        for (int i = 1; i <= n; i++) {
            a[i] = (a[i] + 1) / 2;
        }
        now += 2;
        dfs();
        now -= 2;
        for (int i = 1; i <= n; i++) {
            a[i] = aa[i];
        }
    }

}
bool solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        c[i] = { a[i],b[i] };
    }
    sort(c + 1, c + 1 + n);
    for (int i = 2; i <= n; i++) {
        if (c[i].second < c[i - 1].second) return false;
    }
    p_a[1] = c[1].first, a[1] = c[1].first, b[1] = c[1].second;
    for (int i = 2; i <= n; i++) {
        a[i] = c[i].first, b[i] = c[i].second;
        p_a[i] = c[i].first;
        p_b[i] = c[i].second - c[i - 1].second;
    }
    dfs();
    return true;

}
signed main() {
    solve();
    if (flag) {
        cout << tot << '\n';
    }
    else {
        cout << -1 << "\n";
    }
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 5476kb

input:

5
1 2 3 4 5
6 6 6 6 7

output:

result:

ok 1 number(s): "9"

Test #2:

score: 0

Accepted

time: 1ms

memory: 5480kb

input:

3
2 3 4
1 2 3

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0

Accepted

time: 1ms

memory: 7536kb

input:

2
65536 65537
1 2

output:

result:

ok 1 number(s): "32"

Test #4:

score: 0

Accepted

time: 1ms

memory: 5472kb

input:

1
0
28

output:

result:

ok 1 number(s): "28"

Test #5:

score: 0

Accepted

time: 1ms

memory: 5472kb

input:

1
249912
43

output:

result:

ok 1 number(s): "26"

Test #6:

score: 0

Accepted

time: 1ms

memory: 7524kb

input:

2
52522336 155670
52532336 165670

output:

result:

ok 1 number(s): "10000"

Test #7:

score: 0

Accepted

time: 1ms

memory: 5524kb

input:

2
141839218 538313890
17731054 67290388

output:

result:

ok 1 number(s): "1155"

Test #8:

score: 0

Accepted

time: 1ms

memory: 5484kb

input:

2
678834913 571995689
84855772 71500869

output:

result:

ok 1 number(s): "1411"

Test #9:

score: 0

Accepted

time: 0ms

memory: 5552kb

input:

10
66 0 65 10 40 1 44 29 13 15
84 18 83 28 58 19 62 47 31 33

output:

result:

ok 1 number(s): "18"

Test #10:

score: 0

Accepted

time: 1ms

memory: 5520kb

input:

10
0 74752 70656 67584 29696 44032 80896 22528 1024 52224
2 75 71 68 31 45 81 24 3 53

output:

result:

ok 1 number(s): "12"

Test #11:

score: 0

Accepted

time: 0ms

memory: 3440kb

input:

10
216 232 28 340 0 44 212 172 268 60
59 63 12 90 5 16 58 48 72 20

output:

result:

ok 1 number(s): "7"

Test #12:

score: 0

Accepted

time: 1ms

memory: 3516kb

input:

10
31 36 17 0 61 25 66 0 74 56
47 52 33 16 77 41 82 16 90 72

output:

result:

ok 1 number(s): "16"

Test #13:

score: 0

Accepted

time: 1ms

memory: 3480kb

input:

10
17 6 41 68 34 46 32 64 24 0
36 25 60 87 53 65 51 83 43 19

output:

result:

ok 1 number(s): "19"

Test #14:

score: 0

Accepted

time: 1ms

memory: 3500kb

input:

1000
403 162 111 73 964 795 667 191 80 204 250 672 907 603 523 804 203 729 21 717 788 916 570 41 811 990 730 61 376 162 972 288 12 859 935 290 178 657 199 143 634 417 43 980 232 143 27 669 676 699 215 96 690 293 419 522 841 774 31 875 481 365 402 312 773 882 478 758 345 970 558 174 997 272 557 201 6...

output:

result:

ok 1 number(s): "0"

Test #15:

score: -100

Time Limit Exceeded

input:

1000
286261248 131596288 375914496 430964736 134217728 105381888 484966400 195559424 458752000 325058560 261095424 261095424 396361728 117964800 408420352 285212672 230162432 180355072 356515840 461373440 216006656 489160704 287834112 77594624 314572800 217579520 381157376 456654848 209715200 734003...