글 읽기 - 반례를 알려주시면 감사하겠습니다. (C++, 73%)

give654 1년 전 1

첫번째 태스크를 수행하는 코드의 로직은 다음과 같습니다.

A에서 i번째 비트를 가지는 원소의 갯수 * B에서 i번째 비트를 가지는 원소의 갯수 * 2 ^ i (0-based)

두번째 태스크를 수행하는 코드의 로직은 다음과 같습니다. (검색해서 힌트 받고 떠올렸습니다)

i번째 비트가 0인 A의 원소들 중의 최소, 최대 값

i번째 비트가 1인 A의 원소들 중의 최소, 최대 값

i번째 비트가 0인 B의 원소들 중의 최소, 최대 값

i번째 비트가 1인 B의 원소들 중의 최소, 최대 값

위의 값들을 전부 구해줍니다.

이후

A0 최소 + B0 최소 >= 2^i

A0 최대 + B1 최대 < 2^(i + 1)

A1 최대 + B0 최대 < 2^(i + 1)

A1 최소 + B1 최소 >= 2^i + 2^(i + 1)

위의 4가지 조건을 전부 만족하면 i번째 비트를 결과에 추가해줬습니다.

그러나 약 73% 에서 틀리는데, 정말 왜 틀리는지 모르겠습니다.

도와주시면 감사하겠습니다.

//#define LOCAL_TEST
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int first_query(vector<int>& A, vector<int>& B, int n){

    int ret = 0;
    int mod = 1999;

    vector<int> bits_A(29, 0), bits_B(29, 0);
    for (int i = 0; i < 29; ++i){
        for (int j = 0; j < n; ++j){
            if ((A[j] >> i) & 1) bits_A[i]++;
            if ((B[j] >> i) & 1) bits_B[i]++;
        }
    }

    for (int i = 0; i < 29; ++i){
        int temp = 1;
        temp = (temp * (bits_A[i] % mod)) % mod;
        temp = (temp * (bits_B[i] % mod)) % mod;
        temp = (temp * ((1<<i) % mod)) % mod;
        ret += temp;
        ret %= mod;
    }

    return ret;
}

int second_query(vector<int>& A, vector<int>& B, int n){
    int ret = 0;
    for (int i = 0; i < 29; ++i){
        int curr_bit = 1 << i;
        int next_bit = 1 << (i + 1);

        vector<int> bit_A(4), bit_B(4);
        bit_A[0] = bit_B[0] = next_bit; // i th bit = 0, minimum, initialized INF (unreachable)
        bit_A[1] = bit_B[1] = -1; // i th bit = 0, maximum, initialized -INF
        bit_A[2] = bit_B[2] = next_bit; // i th bit = 1, minimum, initialized INF
        bit_A[3] = bit_B[3] = -1; // i th bit = 1, maximum, initialized -INF

        for (int j = 0; j < n; ++j){

            int t1 = A[j] % next_bit;
            if ((t1 >> i) & 1){
                bit_A[2] = min(bit_A[2], t1);
                bit_A[3] = max(bit_A[3], t1);
            }
            else{
                bit_A[0] = min(bit_A[0], t1);
                bit_A[1] = max(bit_A[1], t1);
            }

            int t2 = B[j] % next_bit;
            if ((t2 >> i) & 1){
                bit_B[2] = min(bit_B[2], t2);
                bit_B[3] = max(bit_B[3], t2);
            }
            else{
                bit_B[0] = min(bit_B[0], t2);
                bit_B[1] = max(bit_B[1], t2);
            }
        }

        if (bit_A[0] == next_bit || bit_B[0] == next_bit || curr_bit <= bit_A[0] + bit_B[0])
            if (bit_A[1] == -1 || bit_B[3] == -1 || bit_A[1] + bit_B[3] < next_bit)
                if (bit_A[3] == -1 || bit_B[1] == -1 || bit_A[3] + bit_B[1] < next_bit)
                    if (bit_A[2] == next_bit || bit_B[2] == next_bit || (curr_bit | next_bit) <= bit_A[2] + bit_B[2])
                        ret |= curr_bit;
    }
    return ret;
}
int main(){

#ifdef LOCAL_TEST
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n;
    cin >> n;
    cin.tie(0);
    ios::sync_with_stdio(false);

    vector<int> A(n), B(n);
    for (auto &p : A) cin >> p;
    for (auto &p : B) cin >> p;

    printf("%d %d", first_query(A, B, n), second_query(A, B, n));
    return 0;
}

give654 1년 전 0

반례 찾았습니다

1

268435456

268435456

댓글을 작성하려면 로그인해야 합니다.