제출 #429022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429022		Tangent	Detecting Molecules (IOI16_molecules)	C++17	46 / 100	1082 ms	4652 KiB

molecules

#include "molecules.h"
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;

#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    map<int, int> cnts;
    forin(weight, w) {
        cnts[weight]++;
    }

    map<int, pii> reached = {{0, {-1, -1}}};
    forin(cnt, cnts) {
        map<int, pii> nreached(reached);
        forin(val, reached) {
            ffor(i, 1, cnt.second + 1) {
                if (val.first + cnt.first * i > u) {
                    break;
                }
                if (nreached.find(val.first + cnt.first * i) != nreached.end()) {
                    continue;
                }
                nreached[val.first + cnt.first * i] = {cnt.first, i};
                if (val.first + cnt.first * i >= l) {
                    map<int, int> needed;
                    int curr = val.first + cnt.first * i;
                    while(curr) {
                        needed[nreached[curr].first] = nreached[curr].second;
                        curr -= nreached[curr].first * nreached[curr].second;
                    }
                    vii res;
                    rep(j, w.size()) {
                        if (needed[w[j]]) {
                            res.emplace_back(j);
                            needed[w[j]]--;
                        }
                    }
                    return res;
                }
            }
        }
        reached = move(nreached);
    }
    return {};
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31