제출 #1267275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267275		nerrrmin	Festival (IOI25_festival)	C++20	39 / 100	66 ms	12528 KiB

festival

#include "festival.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const long long maxn = 2e5 + 10;
long long n, a;

struct coupon
{
    long long cost, type, index;
    coupon(){};
    coupon(long long _cost, long long _type, long long _index)
    {
        cost = _cost;
        type = _type;
        index = _index;
    }
};
bool cmp(coupon c1, coupon c2)
{
    return (c1.cost < c2.cost);
}
vector < coupon > g[5];
vector < long long > sums;
long long dp[maxn];

long long getone(long long tokens)
{
    long long l = 0, r = sums.size()-1, mid = 0, ans = 0;
    while(l <= r)
    {
        mid = (l + r)/2;
        if(sums[mid] <= tokens)
        {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;

    }
    return ans;
}
struct state
{
    long long cnt1, cnt2, cnt3, cnt4;
    state(){};
    state(long long _cnt1, long long _cnt2, long long _cnt3, long long _cnt4)
    {
        cnt1 = _cnt1;
        cnt2 = _cnt2;
        cnt3 = _cnt3;
        cnt4 = _cnt4;
    }
    bool operator==(const state & s)const
    {
        return (cnt1 == s.cnt1 && cnt2 == s.cnt2 && cnt3 == s.cnt3 && cnt4 == s.cnt4);
    }
};
struct stateHash {
    std::size_t operator()(const state& s) const {
        const long long prime = 100;
        std::size_t hash = s.cnt1;  // Starting value
        hash = hash * prime + std::hash<long long>()(s.cnt1+1);
        hash = hash * prime + std::hash<long long>()(s.cnt2+1);
        hash = hash * prime + std::hash<long long>()(s.cnt3+1);
        hash = hash * prime + std::hash<long long>()(s.cnt4+1);
        return hash;
    }
};
unordered_map < state, long long, stateHash > mp;
unordered_map < state, bool, stateHash > valid;
unordered_map < state, long long, stateHash> from;
long long total1, total2, total3, total4;
long long mx;
state best;
void solve_70()
{
    mp[state(-1, -1, -1, -1)] = a;
    valid[state(-1, -1, -1, -1)] = 1;
    mx = 0;
    best = state(-1, -1, -1, -1);
    for (long long p1 = -1; p1 < total1; ++ p1)
    {
        for (long long p2 = -1; p2 < total2; ++ p2)
        {
            for (long long p3 = -1; p3 < total3; ++ p3)
            {
                for (long long p4 = -1; p4 < total4; ++ p4)
                {
                    if(valid[state(p1, p2, p3, p4)] == 0)continue;
                    ///
                    long long all = p1 + 1 + p2 + 1 + p3 + 1 + p4 + 1;
                   // cout << "fff " << from[state(p1, p2, p3, p4)] << endl;
                    if(all > mx)
                    {
                        mx = all;
                        best = state(p1, p2, p3, p4);
                    }
                    long long tokens = mp[state(p1, p2, p3, p4)];

                    if(p1 < total1-1)
                    {
                        long long cost1 = g[1][p1+1].cost;
                        if(tokens >= cost1)
                        {
                            long long tokens1 = tokens - cost1;
                            tokens1 *= 1;
                            state newstate = state(p1+1, p2, p3, p4);

                            if(mp[newstate] <= tokens1)
                            {
                                valid[newstate] = 1;
                                mp[newstate] =  max(mp[newstate], tokens1);
                                from[newstate] = 1;
                            }

                        }

                    }
                    if(p2 < total2-1)
                    {
                        long long cost2 = g[2][p2+1].cost;
                        if(tokens >= cost2)
                        {
                            long long tokens2 = tokens - cost2;
                            if(tokens2 < 1LL * 1e17)tokens2 *= 2;;
                            state newstate = state(p1, p2+1, p3, p4);

                            if(mp[newstate] <= tokens2)
                            {valid[newstate] = 1;
                                mp[newstate] =  max(mp[newstate], tokens2);
                                from[newstate] = 2;
                            }
                        }
                    }
                    if(p3 < total3-1)
                    {
                        long long cost3 = g[3][p3+1].cost;
                        if(tokens >= cost3)
                        {
                            long long tokens3 = tokens - cost3;
                            if(tokens3 < 1LL * 1e17)tokens3 *= 3;
                            state newstate = state(p1, p2, p3+1, p4);

                           if(mp[newstate] <= tokens3)
                            {valid[newstate] = 1;
                                mp[newstate] =  max(mp[newstate], tokens3);
                                from[newstate] = 3;
                            }
                        }
                    }
                    if(p4 < total4-1)
                    {
                        long long cost4 = g[4][p4+1].cost;
                        if(tokens >= cost4)
                        {
                            long long tokens4 = tokens - cost4;
                            if(tokens4 < 1LL * 1e17)tokens4 *= 4;
                            state newstate = state(p1, p2, p3, p4+1);

                            if(mp[newstate] <= tokens4)
                            { valid[newstate] = 1;
                                mp[newstate] =  max(mp[newstate], tokens4);
                                from[newstate] = 4;
                            }
                        }
                    }
                }
            }
        }
    }
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
    a = A;
    n = P.size();

    for (long long i = 0; i < n; ++ i)
    {
        g[T[i]].pb(coupon(P[i], T[i], i));
    }
    for (long long curr = 1; curr <= 4; ++ curr)
        sort(g[curr].begin(), g[curr].end(), cmp);
    total1 = g[1].size();
    total2 = g[2].size();
    total3 = g[3].size();
    total4 = g[4].size();

    if(n <= 70)
    {
        solve_70();
         vector < int > res;
         state curr = best;

         while(from[curr])
         {
             if(from[curr] == 1)
             {
                 res.pb(g[1][curr.cnt1].index);
                curr.cnt1 --;
                continue;
             }
             if(from[curr] == 2)
             {
                 res.pb(g[2][curr.cnt2].index);
                curr.cnt2 --;
                continue;
             }
             if(from[curr] == 1)
             {
                 res.pb(g[1][curr.cnt1].index);
                curr.cnt1 --;
                continue;
             }
             if(from[curr] == 3)
             {
                 res.pb(g[3][curr.cnt3].index);
                curr.cnt3 --;
                continue;
             }
             if(from[curr] == 4)
             {
                 res.pb(g[4][curr.cnt4].index);
                curr.cnt4 --;
                continue;
             }
         }
        reverse(res.begin(), res.end());
        return res;
    }
    sums.pb(0);
    long long pre = 0;
    for (auto &[c, t, i]: g[1])
    {
        pre += c;
       sums.pb(pre);
    }
    vector < int > res;

    long long tokens = a;
    dp[0] = getone(tokens);

    long long mx = 0, best = dp[0];
    long long cnt = 0;
    for (auto &[c, t, i]: g[2])
    {
        if(tokens < c)break;
        cnt ++;
        tokens -= c;
        if(tokens < 1LL * 1e17)tokens *= 2;

      ///  cout << "@ " << cnt << " " << i << endl;
      ///  cout << tokens << " for the ones " << endl;
        dp[cnt] = cnt + getone(tokens);
        if(best < dp[cnt])
        {
            best = dp[cnt];
            mx = cnt;
        }
    }
    for (long long i = 1; i <= mx; ++ i)
        res.pb(g[2][i-1].index);
    for (long long i = 1; i <= best - mx; ++ i)
        res.pb(g[1][i-1].index);
  return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18