제출 #1253327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253327		nvc2k8	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 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;}
///------------------------------------------///
struct equation{
    bitset<100> c;
    ll sum = 0;
    equation() {}
    equation(pair<vector<int>,ll> x, ll X)
    {
        for (auto i:x.fi) c[i] = 1;
        sum = X-x.se;
    }
};

ll a[105];
int t[105], n;
vector<equation> f;

bool check()
{
    FOR(i, 1, n-1) if (!a[i]) return true;
    return false;
}

bool cmp(const equation &x, const equation &y)
{
    int cx = n, cy = n;
    FOR(i, 1, n-1) if (x.c[i])
    {
        cx = i; break;
    }
    FOR(i, 1, n-1) if (y.c[i])
    {
        cy = i; break;
    }
    return cx<cy;
}

void process(int pos)
{
    FOR(i, 1, n-1) if (f[pos].c[i] && a[i]>0)
    {
        f[pos].c[i] = 0; f[pos].sum -= a[i];
    }

    while (f[pos].c.count()>0)
    {
        if (f[pos].c.count()==1)
        {
            int id = 0;
            FOR(i, 1, n-1) if (f[pos].c[i])
            {
                id = i; break;
            }
            a[id] = f[pos].sum;
            int cnt = 0;
            FOR(i, id+1, n-1) if (!a[i]) cnt++;

            if (cnt>0)
            {
                f.pb(equation(transaction(a[id]-1),a[id]-1));
                FOR(i, 1, n-1) if (f.back().c[i]) t[i]++;
                process((int)f.size()-1);
            }
        }
        else
        {
            ll nx = f[pos].sum/f[pos].c.count();
            f.pb(equation(transaction(nx), nx));
            FOR(i, 1, n-1) if (f.back().c[i]) t[i]++;
            process((int)f.size()-1);
        }

        FOR(i, 1, n-1) if (f[pos].c[i] && a[i]>0)
        {
            f[pos].c[i] = 0; f[pos].sum -= a[i];
        }
    }
}

void buy_souvenirs(int N, long long P0)
{
    n = N;
    a[0] = P0;
    f.pb(equation(transaction(P0-1), P0-1));
    FOR(i, 1, n-1) if (f[0].c[i]) t[i]++;

    process(0);

    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: 28 / 28
• Subtask 6: 33 / 33