QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214938#7560. Computer Networkb2ogeymanWA 1ms3448kbC++171.9kb2023-10-15 01:34:562023-10-15 01:34:56

Judging History

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

  • [2023-10-15 01:34:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3448kb
  • [2023-10-15 01:34:56]
  • 提交

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;
#define ln '\n'
#define int ll
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;
        while(m) {
            int need = 0;
            if(m == (1LL << k)) {
                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);
                }
                need = min(need1, need2);
            } else {
                need = 1;
                rep(i, 0, n) {
                    if(a[i] + m >= ((b[i]+1) << k)) {
                        need = 0;
                        break;
                    }
                }
            }
            good = true;
            rep(i, 0, n) {
                a[i] += need*m;
                if(a[i] < (b[i] << k))
                    good=false;
            }
            cur += need;
            if(good)
                break;
            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: 3436kb

input:

5
1 2 3 4 5
6 6 6 6 7

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3448kb

input:

3
2 3 4
1 2 3

output:

31

result:

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