QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207032#7560. Computer Networkucup-team484#WA 1ms3532kbC++172.3kb2023-10-08 03:57:162023-10-08 03:57:17

Judging History

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

  • [2023-10-08 03:57:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3532kb
  • [2023-10-08 03:57:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef __int128 ll;
//typedef long long ll;
typedef pair<int,int> pii;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
  cout << "{";
  if (sz(v)) print(v[0]);
  for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
  cout << "}\n";
}

ll one = 1;

ll my_popcount(ll x){
  unsigned long long a = x>>64;
  unsigned long long b = x & ((one << 64)-1);
  ll res =  __builtin_popcountll(a) + __builtin_popcountll(b);
  //assert(res == __builtin_popcountll(x));
  return res;
}

ll my_clz(ll x){
  unsigned long long a = x>>64;
  unsigned long long b = x & ((one << 64)-1);
  ll res;
  if(a == 0)
    res = 64 + __builtin_clzll(b);
  else
    res = __builtin_clzll(a);
  //assert(res == __builtin_clzll(x));
  return res;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<ll> A(N), B(N);
  for(int i=0; i<N; i++){
    int x;
    cin >> x;
    A[i] = x;
  }
  for(int i=0; i<N; i++){
    int x;
    cin >> x;
    B[i] = x;
  }
  //print(A);
  //print(B);
  ll res = -1;
  for(int k=0; k<80; k++){
    ll l = 0, h = one<<120;
    for(int i=0; i<N; i++){
      ll low = (B[i] << k) - A[i];
      ll hi = ((B[i]+1) << k) - 1 - A[i];
      l = max(l, low);
      h = min(h, hi);
      //cout << l << "," << h << " ";
    }
    //cout << endl;
    //cout << k << ": " << l << " - " << h << endl;
    if(l > h)
      continue;
    ll cur = k;

    ll diff, first_digit;

    if(l >= (one<<(k+1))){
      cur += (l>>(k+1)) * 2;
      if((l >> (k+1)) != (h >> (k+1))){
        l &= (one<<(k+1))-1;
        if(l <= (one<<k))
          cur++;
        else
          cur += 2;
        goto DONE;
      }
      else{
        l &= (one<<(k+1))-1;
        h &= (one<<(k+1))-1;
      }
    }
    //cout << ".. " << l << " -- " << h << ": " << cur << endl;
    diff = l ^ h;
    if(diff == 0){
      
    }
    else{
      //first_digit = 1ll<<(63-my_clz(diff));
      first_digit = one<<(127-my_clz(diff));
      h &= ~(first_digit-1);
    }
    cur += my_popcount(h);

DONE:
    //cout << "-> " << cur << endl;
    if(res == -1 || cur < res)
      res = cur;
  }
  cout << (long long) res << endl;
}

詳細信息

Test #1:

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

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

input:

3
2 3 4
1 2 3

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

2
65536 65537
1 2

output:

32

result:

ok 1 number(s): "32"

Test #4:

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

input:

1
0
28

output:

28

result:

ok 1 number(s): "28"

Test #5:

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

input:

1
249912
43

output:

26

result:

ok 1 number(s): "26"

Test #6:

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

input:

2
52522336 155670
52532336 165670

output:

10000

result:

ok 1 number(s): "10000"

Test #7:

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

input:

2
141839218 538313890
17731054 67290388

output:

1155

result:

ok 1 number(s): "1155"

Test #8:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

2
678834913 571995689
84855772 71500869

output:

1411

result:

ok 1 number(s): "1411"

Test #9:

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

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: -100
Wrong Answer
time: 0ms
memory: 3532kb

input:

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

output:

13

result:

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