QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214996#7560. Computer NetworkTheOneYouWant#WA 1ms3560kbC++172.0kb2023-10-15 02:03:102023-10-15 02:03:11

Judging History

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

  • [2023-10-15 02:03:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3560kb
  • [2023-10-15 02:03:10]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
#define ln '\n'
#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 pair<int, int> pii;
typedef vector<int> vi;
const int INF = 1e9+7;

int n;
vi a, aa, b;

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    a.resize(n);
    aa.resize(n);
    b.resize(n);
    rep(i, 0, n)
        cin >> aa[i];
    rep(i, 0, n)
        cin >> b[i];
    int ans = INF;
    rep(k, 0, 32) {
        rep(i, 0, n)
            a[i] = aa[i];
        bool flag = false;
        rep(i, 0, n)
            if(a[i] >= (b[i]+1)*(1LL << k))
                flag = true;
        if(flag)
            continue;
        int m = (1LL << k);
        int cur = 0;
        bool good = true;

        int need1 = INF, need2 = 0;
        rep(i, 0, n) {
            need1 = min(need1, max(0LL, (b[i]*(1LL << k) + (1LL << k) - 1 - a[i]))/m);
            need2 = max(need2, max(0LL, (b[i]*(1LL << k) + m - 1 - a[i]))/m);
        }
        int need = min(need1, need2);
        good = true;
        rep(i, 0, n) {
            a[i] += need*m;
            if(a[i] < (b[i] << k))
                good = false;
        }
        cur += need;
        if(good) {
            ans = min(ans, cur);
        } else {
            m >>= 1;
            int mn = INF, mx = 0;
            rep(i, 0, n) {
                mn = min(mn, ((b[i]+1) << k) - a[i]);
                mx = max(mx, (b[i] << k) - a[i]);
            }
            while(m) {
                if(m < mn) {
                    mn -= m;
                    mx -= m;
                    cur++;
                }
                good = false;
                if(mx <= 0)
                    good=true;
                m >>= 1;
            }
        }
        if(good) {
            ans = min(ans, cur + k);
        }
    }
    if(ans == INF)
        cout << -1 << ln;
    else 
        cout << ans << ln;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1 2 3 4 5
6 6 6 6 7

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

3
2 3 4
1 2 3

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

2
65536 65537
1 2

output:

32

result:

ok 1 number(s): "32"

Test #4:

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

input:

1
0
28

output:

28

result:

ok 1 number(s): "28"

Test #5:

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

input:

1
249912
43

output:

13

result:

wrong answer 1st numbers differ - expected: '26', found: '13'