제출 #1279889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279889		banme	선물 (IOI25_souvenirs)	C++20	100 / 100	16 ms	8256 KiB

souvenirs

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

long long solved[1000];
long long equations [1000][1000];
long long br[1000];







void update(long long N){
    for(int i=1;i<N;i++){
        if(equations[N][i]==1){
            equations[0][i] -= solved[N];
        }
    }
}

long long neweq (long long i,long long nums){
    if(nums==1){
        return equations[0][i]-1;
    }else{
        return equations[0][i]/nums;
    }

}


void solve(int N,long long P0){

    if(N==1){return;}
    while(equations[N][N]!=1){
        int i = N;
        while(equations[i][i]!=1){
            i=i-1;
        }
        int nums =0;
        for(int j=i;j<=N;j++){
            if(equations[j][i]==1){
                nums++;
            }
        }
        long long x;
        pair<vector<int>,long long> s;
        if(i!=0){
            s = transaction(neweq(i,nums));
            x = neweq(i,nums);
        }else{
            s = transaction(P0-1);
            x = P0-1;

        }
        //cout<<x<<" amogus "<<nums<<endl;
        long long newe=s.first[0]+1;
        equations[0][newe] = x - s.second;
        for(int t = 0;t<s.first.size();t++){
            equations[s.first[t]+1][newe] = 1;
            br[s.first[t]]++;
            if(s.first[t] >= N) {
            	equations[0][newe]-=solved[s.first[t]+1];
            }
        }


    }
    /*for(int i = 1; i <= N; i++) {
        for(int j = 0; j <= N; j++) {
            cout << equations[j][i] << " ";
        }
        cout << endl;
    }
    cout<<endl;*/
    solved[N] = equations[0][N];
    update(N);
    solve(N-1,P0);
}

void buy_souvenirs(int N, long long P0) {
    for(int i=0;i<1000;i++){
        solved[i]=0;
        br[i]=0;
    for(int j=0;j<1000;j++){
        equations[i][j]=0;
    }

    }
    equations[0][0] = 1;
    solve(N,P0);
    for(int i=0;i<N;i++){
        for(int j =0;j<i-br[i];j++){
            transaction(solved[i+1]);
        }
    }
  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