Submission #1277878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277878		Andrey	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	14 ms	396 KiB

souvenirs

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

vector<long long> ans(0);
vector<long long> br(0);
long long n;

void dfs(long long a, long long x, pair<vector<int>, long long> c) {
    if(a == n-1) {
        ans[n-1] = x-c.second;
        br[n-1]++;
        return;
    }
    while(ans[a+1] == -1) {
        long long sb = x-c.second,z = c.first.size();
        for(long long v: c.first) {
            if(ans[v] != -1) {
                sb-=ans[v];
                z--;
            }
        }
        long long x1 = (sb+z-1)/z-1;
        pair<vector<int>,long long> d = transaction(x1);
        dfs(d.first[0],x1,d);
    }
    long long sb = x-c.second;
    for(long long v: c.first) {
        if(v != a) {
            sb-=ans[v];
        }
        br[v]++;
    }
    ans[a] = sb;
}

void buy_souvenirs(int N, long long p0) {
    ans.clear();
    br.clear();
    n = N;
    for(long long i = 0; i < n; i++) {
        ans.push_back(-1);
        br.push_back(0);
    }
    ans[0] = p0;
    pair<vector<int>, long long> c = transaction(p0-1);
    dfs(1,p0-1,c);
    for(long long i = 0; i < n; i++) {
        for(long long j = 0; j < i-br[i]; j++) {
            transaction(ans[i]);
        }
    }
}

• 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