글 읽기 - 반례 부탁드립니다 제발류.. C++

lsc4719 3년 전 0

맞(제 코드는 맞는 것 같은데) 왜(어째서..) 틀(틀린다고 나올까요..?)

반례 부탁드립니다..

혹시 가능하다면, 커피 보내드리겠습니다.

----

내용추가

전체 최대 32개에서

16, 16개씩 둘로 나누고

2^16번 돌면서 각각 lg(2^16) 바이너리 서치를 하는 meet in the middle 코드를 짠거같은데..

틀.ㄹ렸.습니다...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Solution 
{
    long long set_size;
    vector<long long> elm_costs;
    vector<long long> elm_values;
    long long value_needed;
    long long deposit;

    int left_half_size;
    int right_half_size;
    vector<long long> left_half_costs;
    vector<long long> left_half_values;
    vector<long long> right_half_values;
    vector<pair<long long, long long>> right_cost_value_pairs; 
    vector<long long> right_half_costs_uniq; // 좌표압축
    vector<long long> right_half_cost_to_max_value;

    void input()
    {
        cin >> set_size;

        for(int i=0;i<set_size;i++)
        {
            long long cost;
            cin >> cost;
            elm_costs.push_back(cost);
        }
        for(int i=0;i<set_size;i++)
        {
            long long value;
            cin >> value;
            elm_values.push_back(value);
        }

        cin >> value_needed;
        
        deposit = 0;
        int cnt;
        cin >> cnt;
        for(int i=0;i<cnt;i++)
        {
            int idx;
            cin >> idx;
            idx -= 1;
            deposit += elm_costs[i];
        }
    }

    void prepare()
    {
        left_half_size = set_size / 2; //이거 중요..
        right_half_size = set_size - left_half_size;

        for(int i=0;i<(1<<left_half_size);i++)
        {
            long long left_half_cost = 0;
            long long left_half_value = 0;
            for(int j=0;j<left_half_size;j++)
            {
                int pos = left_half_size - 1 - j;
                if (i & (1 << j))
                {
                    left_half_cost += elm_costs[pos];
                    left_half_value += elm_values[pos];
                }
            }

            left_half_costs.push_back(left_half_cost);
            left_half_values.push_back(left_half_value);
        }

        for(int i=0;i<(1<<right_half_size);i++)
        {
            long long right_half_cost = 0;
            long long right_half_value = 0;
            for(int j=0;j<right_half_size;j++)
            {
                int pos = set_size - 1 - j;
                if(i & (1 << j))
                {
                    right_half_cost += elm_costs[pos];
                    right_half_value += elm_values[pos];
                }
            }

            right_half_costs_uniq.push_back(right_half_cost);

            right_cost_value_pairs.push_back(make_pair(right_half_cost, right_half_value));
        }

        sort(right_half_costs_uniq.begin(), right_half_costs_uniq.end());
        right_half_costs_uniq.erase(unique(right_half_costs_uniq.begin(), right_half_costs_uniq.end()), right_half_costs_uniq.end());

        right_half_cost_to_max_value.resize(right_half_costs_uniq.size(), 0);

        sort(right_cost_value_pairs.begin(), right_cost_value_pairs.end());
               
        for(int i=0, idx=0;i<right_cost_value_pairs.size();i++)
        {
            long long right_half_cost = right_cost_value_pairs[i].first;
            long long right_half_value = right_cost_value_pairs[i].second;

            while(right_half_costs_uniq[idx] != right_half_cost)
            {
                idx += 1;
            }

            right_half_cost_to_max_value[idx] = max(right_half_cost_to_max_value[idx], right_half_value);
        }

        for(int i=1;i<right_half_cost_to_max_value.size();i++)
        {
            right_half_cost_to_max_value[i] = max(right_half_cost_to_max_value[i], right_half_cost_to_max_value[i-1]);
        }
    }

    bool g(int idx, long long money)
    {
        return (0LL <= (money - right_half_costs_uniq[idx]));
    }

    bool f(long long money)
    {
        long long max_value = 0;
        for(int left_half=0;left_half<(1<<left_half_size);left_half++)
        {
            long long left_half_cost = left_half_costs[left_half];
            long long left_half_value = left_half_values[left_half];

            long long remain_money = money - left_half_cost;

            int lo = 0;
            int hi = right_half_costs_uniq.size()-1;
            while(lo < hi)
            {
                int mid = (lo + hi + 1) / 2;
                if(g(mid, remain_money))
                {
                    lo = mid;
                }
                else
                {
                    hi = mid - 1;
                }                
            }

            if(!g(lo, remain_money)) continue;

            max_value = max(max_value, left_half_value + right_half_cost_to_max_value[lo]);
        }
        return (value_needed <= max_value);
    }

    long long solve()
    {
        input();
        prepare();

        const long long INF = 1e10;

        long long lo = 0;
        long long hi = INF;
        while(lo < hi)
        {
            long long mid = (lo + hi) / 2;

            if (f(mid))
            {
                hi = mid; 
            }
            else
            {
                lo = mid + 1;
            }            
        }

        if(lo == INF) return -1;
        return max(0LL, lo-deposit);
    }
};

int main()
{
    Solution s;
    cout << s.solve() << endl;
    return 0;
}

lsc4719 3년 전 0

입력 받는 부분 문제였습니다;;

        for(int i=0;i<cnt;i++)
        {
            int idx;
            cin >> idx;
            idx -= 1;
            deposit += elm_costs[i];
        }

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

문제

문제

출처

ICPC

반례 부탁드립니다 제발류.. C++

lsc4719 3년 전 0

lsc4719 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말