QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207030#7560. Computer Networkucup-team484#WA 0ms3632kbC++172.3kb2023-10-08 03:54:012023-10-08 03:54:01

Judging History

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

  • [2023-10-08 03:54:01]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3632kb
  • [2023-10-08 03:54:01]
  • 提交

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 = __builtin_clzll(a);
  else
    res = 64 + __builtin_clzll(b);
  //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<<(64-my_clz(diff));
      first_digit = one<<(128-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: 0ms
memory: 3572kb

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

input:

3
2 3 4
1 2 3

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

2
65536 65537
1 2

output:

32

result:

ok 1 number(s): "32"

Test #4:

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

input:

1
0
28

output:

28

result:

ok 1 number(s): "28"

Test #5:

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

input:

1
249912
43

output:

25

result:

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