Submission #1253258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253258		nvc2k8	Souvenirs (IOI25_souvenirs)	C++20	39 / 100	11 ms	412 KiB

souvenirs

#include <bits/stdc++.h>
#define TASK "sourvenirs"
#include "souvenirs.h"
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define all(C) C.begin(), C.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int INT_LIM = 2147483647;
const ll LL_LIM = 9223372036854775807;
template <typename X> bool minimize(X &x, const X &y) {if (x>y){x = y; return true;}return false;}
template <typename X> bool maximize(X &x, const X &y) {if (x<y){x = y; return true;}return false;}
///------------------------------------------///

ll a[105];
int t[105];

void buy_souvenirs(int N, long long P0)
{
    if (N==2)
    {
        transaction(P0-1);
        return;
    }
    if (N==3)
    {
        pair<vector<int>, ll> v = transaction(P0-1);
        if (v.fi.size()==1)
        {
            ll P1 = P0-1-v.se;
            transaction(P1-1);
            transaction(P1-1);
        }
        else
        {
            ll P2 = (P0-1-v.se)/2;
            transaction(P2);
        }
        return;
    }
    if (P0==N)
    {
        FOR(i, 1, N-1)
        {
            FOR(j, 1, i) transaction(N-i);
        }
        return;
    }

    ll cur = P0-1;
    FOR(i, 1, N-1)
    {
        if (t[i]>0) break;
        pair<vector<int>, ll> v = transaction(cur);
        for (auto u:v.fi) t[u]++;
        ll psum = cur-v.se;
        if (v.fi.size()==1)
        {
            a[i] = psum;
            cur = psum-1;
            continue;
        }
        a[i] = psum-1;
        a[N-1] = 1;
        cur = a[i]-1;
    }

    FOR(i, 1, N-1)
    {
        FOR(j, t[i]+1, i) transaction(a[i]);
    }

    return;
}

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