Submission #1249903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249903		Jakub_Wozniak	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<vector <int> ,ll> pvl;
#define st first
#define nd second
const int maxn = 109;
ll P[maxn];
int ile[maxn];
int ng;

pvl zap(ll L)
{
  pvl temp = transaction(L);
  for(auto p : temp.st)
  {
    ile[p]++;
  }
  return temp;
}

void rek(vector <int> v , ll sum)
{
  if(v.size() == 1)
  {
    P[v[0]] = sum;
    if(v[0] == ng-1)return ;
    if(P[v[0]+1] == 0)
    {
      pvl temp = zap(P[v[0]]-1);
      rek(temp.st , P[v[0]]-1-temp.nd);
    }
    return ;
  }
    //cerr << "NEW: ";
    //for(auto p : v )cerr << p << ' ' ; cerr << '\n';
    //for(auto p : v )cerr << P[p] << ' ' ; cerr << '\n';
    //cerr << "  " << sum << endl;
    //cerr <<"END\n";
    vector <int> nv;
    bool czyz = 0;
    for(auto p : v)
    {
      if(P[p] != 0)
      {
        sum -= P[p];
        czyz = 1;
      }
      else
      {
        nv.push_back(p);
      }
    }

    if(czyz)
    {
      rek(nv,sum);
      return ;
    }

    if(v.size() == 0)return ;
    if(v.size() == 1)
    {
      P[v[0]] = sum;
      return ;
    }
    

    ll sr = sum/(v.size());
    pvl temp = zap(sr);
    rek(temp.st , sr-temp.nd);
    rek(v,sum);
}


void buy_souvenirs(int N, long long P0) 
{
  ng = N;
  P[0] = P0;
  for(int i = 1; i < N ; i++)
  {
    if(P[i] != 0)continue;
    pvl temp = zap(P[i-1]-1);
    rek(temp.st , P[i-1]-1-temp.nd); 
  }

  for(int i = 1; i < N ; i++)
  {
    while(ile[i] < i)
    {
      zap(P[i]);
    }
  }
  
  return;
}


/*
9
100 59 58 57 9 8 7 6 5
*/

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