QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#303324#7560. Computer NetworkUrvuk3TL 0ms3796kbC++141.8kb2024-01-12 07:01:352024-01-12 07:01:36

Judging History

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

  • [2024-01-12 07:01:36]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3796kb
  • [2024-01-12 07:01:35]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9,MOD=1e9+7;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
//#define endl "\n"
#define pb push_back

void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}

template<typename T,typename V>
void PRINT(pair<T,V>& x){
    cerr<<"{";
    PRINT(x.fi);
    cerr<<",";
    PRINT(x.se);
    cerr<<"}";
}
template<typename T>
void PRINT(T &x){
    int id=0;
    cerr<<"{";
    for(auto _i:x){
        cerr<<(id++ ? "," : "");
        PRINT(_i);
    }
    cerr<<"}";
}
void _PRINT(){
    cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
    PRINT(h);
    if(sizeof...(t)) cerr<<", ";
    _PRINT(t...);
}

#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)

void Solve(){
    int N; cin>>N;
    vector<ll> a(N+1),b(N+1);
    for(int i=1;i<=N;i++) cin>>a[i];
    for(int i=1;i<=N;i++) cin>>b[i];
    ll res=1e18;
    for(ll k=0;k<=30;k++){
        ll L=0,R=1e18;
        for(int i=1;i<=N;i++){
            L=max(L,b[i]*(1<<k)-a[i]);
            R=min(R,b[i]*(1<<k)+(1<<k)-a[i]-1);
        }
        if(L>R) continue;
        if(L==0) res=min(res,k);
        while(L<=R){
            res=min(res,(L>>k)+__builtin_popcount(L&((1<<k)-1))+k);
            L+=L&-L;
        }
    }
    cout<<(res==1e18 ? -1 : res)<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t; t=1;
    //cin>>t;
    while(t--){
        Solve();
    }
    return 0;
}

詳細信息

Test #1:

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

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

input:

3
2 3 4
1 2 3

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

2
65536 65537
1 2

output:

32

result:

ok 1 number(s): "32"

Test #4:

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

input:

1
0
28

output:

28

result:

ok 1 number(s): "28"

Test #5:

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

input:

1
249912
43

output:

26

result:

ok 1 number(s): "26"

Test #6:

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

input:

2
52522336 155670
52532336 165670

output:

10000

result:

ok 1 number(s): "10000"

Test #7:

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

input:

2
141839218 538313890
17731054 67290388

output:

1155

result:

ok 1 number(s): "1155"

Test #8:

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

input:

2
678834913 571995689
84855772 71500869

output:

1411

result:

ok 1 number(s): "1411"

Test #9:

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

input:

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

output:

18

result:

ok 1 number(s): "18"

Test #10:

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

input:

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

output:

12

result:

ok 1 number(s): "12"

Test #11:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #12:

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

input:

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

output:

16

result:

ok 1 number(s): "16"

Test #13:

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

input:

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

output:

19

result:

ok 1 number(s): "19"

Test #14:

score: -100
Time Limit Exceeded

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: