제출 #1309768

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309768		Joon_Yorigami	선물 (IOI25_souvenirs)	C++17	3 / 100	1070 ms	400 KiB

souvenirs

#include <bits/stdc++.h>
#include "souvenirs.h"
#include <utility>
#include <vector>
using namespace std;
using ll=long long;

constexpr int maxn = 105;
ll need[maxn];
ll prices[maxn];

//std::pair<std::vector<int>, long long> transaction(long long M)

bool checkIfSolved(int n)
{
  bool ret=true;
  for(int i=0;i<n;i++)
    ret&=prices[i]>0;
  return ret;
}

void buy_souvenirs(int N, long long P0) {
  for(int i=0;i<N;i++)
    prices[i]=0;
  for(int i=0;i<N;i++)
    need[i]=i;
  prices[0]=P0;
  vector<pair<vector<int>,ll>> multisets;
  std::pair<std::vector<int>, long long> res;
  while(!checkIfSolved(N))
  {
    bool solvedOne=true;
    while(solvedOne)
    {
      solvedOne=false;
      vector<pair<vector<int>,ll>> newMultisets;
      for(auto pa:multisets)
      {
        vector<int> indices=pa.first;
        int cost=pa.second;
        vector<int> leftover;
        for(auto idx:indices)
        {
          if(prices[idx]>0)
          {
            cost-=prices[idx];
          }
          else
          {
            leftover.push_back(idx);
          }
        }
        if(leftover.size()==0)
          continue;
        if(leftover.size()==1)
        {
          prices[leftover[0]]=cost;
          solvedOne=true;
        }
        else
        {
          newMultisets.push_back({leftover,cost});
        }
      }
      multisets=newMultisets;
    }
    if(checkIfSolved(N))
      break;
    /*
    for(int i=0;i<N;i++)
      cout << need[i] << ' ';
    cout << endl;
    for(int i=0;i<N;i++)
      cout << prices[i] << ' ';
    cout << endl;
    */
    int curr;
    int needToSolve;
    curr=N-1;
    while(prices[curr]>0)
      curr--;
    needToSolve=curr;
    while(prices[curr]==0)
      curr--;
    vector<int> arr;
    vector<int> barr;
    int used;
    ll x;
    x=prices[curr]-1;
    while(prices[needToSolve]==0)
    {
      /*
      for(int i=0;i<N;i++)
        cout << need[i] << ' ';
      cout << endl;
      for(int i=0;i<N;i++)
        cout << prices[i] << ' ';
      cout << endl;
      cout << x << endl;
      */
      res=transaction(x);
      arr=res.first;
      vector<int>().swap(barr);
      used=x-res.second;
      for(auto num:arr)
      {
        need[num]-=1;
        if(prices[num]>0)
        {
          used-=prices[num];
        }
        else
        {
          barr.push_back(num);
        }
      }
      if(barr.size()==1)
      {
        prices[barr[0]]=used;
        x=used-1;
      }
      else
      {
        x=used/barr.size();
        multisets.push_back({barr,used});
      }
    }
  }
  for(int i=0;i<N;i++)
  {
    while(need[i]>0)
    {
      transaction(prices[i]);
      need[i]-=1;
    }
  }
  return;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 4
• Subtask 2: 3 / 3
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33