글 읽기 - 7453 합이 0이 되는 네 정수 반례 하나만 부탁드립니다 (C++)

roeniss 4년 전 1

거의 다 온 것 같은데, 틀렸다고 떠서 부디 도움을 요청드립니다.

답이 안나오는 반례 딱 하나면 됩니다.. 제발...부디...

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define ll long long

ll a, b, c, d;
int N;
vector<ll> va, vb, vc, vd, v1, v2;
vector<ll>::iterator iter;

ll get_lower_bound(ll high, ll target) {
    ll low = 0, mid, result = high;
    while (low <= high) {
        mid = (low + high) / 2;
        ll now_val = v2[mid];
        if (now_val < target) {
            low = mid + 1;
        } else { // now_val == target
            result = mid;
            high = mid - 1;
        }
    }
    return result;
}

ll binary_search(ll x) {
    ll low = 0, mid, high = v2.size() - 1;
    ll target = 0 - x, result = 0;
    bool check = false;
    while (low <= high) {
        mid = (low + high) / 2;
        ll now_val = v2[mid];
        if (now_val <= target) {
            if (now_val == target) {
                check = true;
                result = low;
            }
            low = mid + 1;
        } else { // now_val > target
            high = mid - 1;
        }
    }
    if (!check) return 0;
    ll lb = get_lower_bound(result, target);
    return result - lb + 1;
}

int main() {
    scanf("%d", &N);
    va.resize(N);
    vb.resize(N);
    vc.resize(N);
    vd.resize(N);
    v1.resize(N * N);
    v2.resize(N * N);
    for (int i = 0; i < N; ++i) {
        scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
        va[i] = a;
        vb[i] = b;
        vc[i] = c;
        vd[i] = d;
    }
    int cnt = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            v1[cnt] = va[i] + vb[j];
            v2[cnt] = vc[i] + vd[j];
            cnt++;
        }
    }
    sort(v2.begin(), v2.end());

    ll result = 0;
    for (int i = 0; i < N * N; ++i) {
        ll tmp = v1[i];
        ll check = binary_search(tmp);
        if (check > 0) result += check;
    }
    
    printf("%lld", result);
    return 0;
}

harinboy 4년 전 8

반례만 드리겠습니다.

0 -100 2 2

0 -4 2 4

정답: 4

오답: 2

의도하신 코드에서 딱 한 줄을 틀리신게 아닌가... 싶네요.

roeniss 4년 전 1

방금 전 그 딱 한 줄을 찾아내서 기쁜 마음에 "안알려주셔도 됩니다~~!" 하러 왔는데 그 사이에 @harinboy님이... 주륵... 감사합니다!

wook3024 4년 전 1

감사합니다 감사합니다 정말 감사합니다 ㅠㅠㅠㅠㅠㅠㅠ휴

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

문제

문제

출처

ICPC

7453 합이 0이 되는 네 정수 반례 하나만 부탁드립니다 (C++)

roeniss 4년 전 1

harinboy 4년 전 8

roeniss 4년 전 1

wook3024 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말