Submission #1283365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283365		Luvidi	Souvenirs (IOI25_souvenirs)	C++20	53 / 100	13 ms	404 KiB

souvenirs

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

#define ll long long
#define fs first
#define sc second

void buy_souvenirs(int n, long long p0) {
    vector<int> vr;
    ll rr;
    int a[n];
    memset(a,0,sizeof(a));
    ll p[n];
    memset(p,0,sizeof(p));
    p[0]=p0;
    pair<vector<int>,ll> rs,tt[n];
    vector<int> id={0};
    ll x=p0;
    while(id[0]!=n-1){
        if(id.size()==1)x--;
        else x/=2;
        rs=transaction(x);
        id=rs.fs,x-=rs.sc;
        for(int i:id){
            a[i]++;
            if(i!=id[0])tt[id[0]].fs.push_back(i);
        }
        tt[id[0]].sc=x;
    }
    // for(int i=0;i<n;i++)if(tt[i].sc){
    //     cout<<i<<": ";
    //     for(int j:tt[i].fs)cout<<j<<' ';
    //     cout<<"| "<<tt[i].sc<<'\n';
    // }
    for(int i=n-1;i;i--){
        if(tt[i].sc){
            p[i]=tt[i].sc;
            for(int j:tt[i].fs)p[i]-=p[j];
        }else{
            rs=transaction(p[i+1]*2);
            vr=rs.fs,rr=rs.sc;
            p[i]=p[i+1]*2-rr;
            for(int j:vr){
                a[j]++;
                if(i!=j)p[i]-=p[j];
            }
        }
    }

    for(int i=1;i<n;i++){
        for(;a[i]<i;a[i]++){
            transaction(p[i]);
        }
    }
}

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