Submission #757260

#	Time	Username	Problem	Language	Result	Execution time	Memory
757260		Seb	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	1 ms	212 KiB

molecules

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

using namespace std;

typedef long long ll;

struct rango{
    ll L, R;
    rango(ll a, ll b) {
        L = a;
        R = b;
    }
};

rango merger(rango a, rango b) {
    rango ans(0,0);
    ans.L = min(a.L,b.L);
    ans.R = max(a.R,b.R);
    return ans;
}

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    ll n = w.size();
    ll in[n],L=0,R=n-1,idx=0;
    for (int i=0;i<n;i++) in[i] = i;
    sort(in,in+n, [&] (ll a, ll b) {return w[a] < w[b];});
    vector <int> ans;
    vector <rango> ran;
    ran.push_back(rango(l,u));
    for (int i=0;i<n;i++) {
        if (i%2==0) {
            ran.push_back(rango(ran[ran.size()-1].L-w[in[L]],ran[ran.size()-1].R-w[in[L]]));
            for (int j=ran.size()-1;j>idx;j--) ran[j] = merger(ran[j],rango(ran[j-1].L-w[in[L]],ran[j-1].R-w[in[L]]));
            idx++;
            L++;
        }
        else {
            ran.push_back(rango(ran[ran.size()-1].L-w[in[R]],ran[ran.size()-1].R-w[in[R]]));
            for (int j=ran.size()-1;j>idx;j--) ran[j] = merger(ran[j],rango(ran[j-1].L-w[in[R]],ran[j-1].R-w[in[R]]));
            idx++;
            R--;
        }
        if (ran[ran.size()-1].L <= 0 && ran[ran.size()-1].R >= 0) {
            L--;
            R++;
            while (L>0) {
                ans.push_back(in[L]);
                L--;
            }
            while (R<n) {
                ans.push_back(in[R]);
                R++;
            }
        }
    }
    return ans;
}

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