Submission #131939

#	Time	Username	Problem	Language	Result	Execution time	Memory
131939		choikiwon	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	63 ms	7160 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MN = 200010;

int N;
pii W[MN];
ll psum[MN];

ll calc(int l, int r) {
    return psum[r] - (l? psum[l - 1] : 0);
}

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    N = w.size();
    for(int i = 0; i < N; i++) {
        W[i] = pii(w[i], i);
    }
    sort(W, W + N);

    for(int i = 0; i < N; i++) {
        psum[i] = W[i].first;
        if(i) psum[i] += psum[i - 1];
    }

    for(int i = 0; i < N; i++) {
        if(l <= W[i].first && W[i].first <= u) return vector<int>(1, W[i].second);
    }
    bool ok = false;
    for(int i = 0; i < N; i++) {
        if(W[i].first < l) {
            ok = true;
            break;
        }
    }
    if(!ok) return vector<int>(0);

    for(int i = 1; i <= N; i++) {
        if(calc(N - i, N - 1) < l) continue;
        if(calc(0, i - 1) > u) break;

        for(int j = 0; j <= N - i; j++) {
            ll t = calc(j, j + i - 1);
            if(l <= t && t <= u) {
                vector<int> ret;
                for(int k = j; k < j + i; k++) ret.push_back(W[k].second);
                return ret;
            }
        }
    }

    return std::vector<int>(0);
}

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