Submission #1264298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264298		anango	Souvenirs (IOI25_souvenirs)	C++20	18 / 100	0 ms	412 KiB

souvenirs

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

vector<int> known;

void buy_souvenirs(int32_t N, long long P0) {
    //let's say that you start by doing P[0]-1
    //this guarantees that you buy the first souvenir
    //then you can repeat the same process with the rest of the souvenirs
    //ok so our method is
    //start with P[0]-1
    //then let S be the set of bought souvenirs
    //take the average of S (it's known from the given info)
    //transaction based on this
    //then say the first souvenir bought is i, it means that from 1 to i-1 the souvenirs are more than S
    //and from i to N-1 the souvenirs are less than S
    //solve i to N-1 recursively with the same process
    //and then solve 1 to i-1 also recursively using the info from i to N-1
    //and then once we know all the values we can do the required transactions with full information

    //N=2 sol
    known=vector<int>(N, -1);
    pair<vector<int32_t>, long long> res = transaction(P0-1);
    vector<int> bought(res.first.begin(), res.first.end());
    int change = res.second;
    int numbought = bought.size();
    if (numbought==1) {
        known[0] = P0-1-change;
        pair<vector<int32_t>, long long> res = transaction(known[0]-1);
        res = transaction(known[0]-1);
    }
    else {
        pair<vector<int32_t>, long long> res = transaction((P0-1-change)/2);
    }
    return;
}

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