Submission #1254257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254257		KLPP	선물 (IOI25_souvenirs)	C++20	100 / 100	14 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include<bits/stdc++.h>

using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;


int n;
vector<lld> values;
vector<pair<vector<int>,lld > > eqs;
vector<int> tot;



void buy_souvenirs(int N, long long P0) {
  n=N;
  values.clear();
  eqs.clear();
  tot.clear();
  tot.resize(n,0);
  values.resize(n,-1);
  vector<int> Frst(n,0);
  Frst[0]=1;
  eqs.push_back({Frst,P0});
  while(true){
    sort(eqs.begin(),eqs.end());
    bool W=true;
    trav(a,values){
      if(a==-1)W=false;
    }
    if(W){
      break;
    }
    int idx=-1;
    for(int i=0;i<eqs.size();i++){
      bool cl=true;
      int pos=n-1-i;
      rep(j,0,pos){
        if(eqs[i].first[j]!=0)cl=false;
      }
      if(!cl){
        idx=i;
        rep(j,pos+1,n){
          if(values[j]!=-1 && eqs[i].first[j]==1){
            eqs[i].first[j]=0;
            eqs[i].second-=values[j];
          }
        }
        break;
      }else{
        rep(j,pos+1,n){
          assert(values[j]!=-1);
          if(eqs[i].first[j]==1){
            eqs[i].first[j]=0;
            eqs[i].second-=values[j];
          }
        }
        values[pos]=eqs[i].second;
      }
    }
    // trav(a,eqs){
      // trav(b,a.first){
        // cout<<b<<" ";
      // }
      // cout<<": "<<a.second<<endl;
    // }cout<<"==="<<endl;
    
    W=true;
    trav(a,values){
      if(a==-1)W=false;
    }
    if(W){
      break;
    }
    
    
    int cnt=0;
    rep(j,0,n){
      cnt+=eqs[idx].first[j];
    }
    lld val=eqs[idx].second;
    if(val%cnt==0){
      val=val/cnt-1;
    }else{
      val=val/cnt;
    }
    
    pair<vector<int>,lld> P=transaction(val);
    vector<int> row(n,0);
    trav(a,P.first)row[a]=1,tot[a]+=1;
    eqs.push_back({row,val-P.second});
  }
  
  rep(i,1,n){
    while(tot[i]<i){
      transaction(values[i]);
      tot[i]++;
    }
  }
  
  return;
}

• 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