Submission #232942

#	Time	Username	Problem	Language	Result	Execution time	Memory
232942		MarWarPL	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	66 ms	5752 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;
#define FOR(i,x,y) for(int i=(int)(x);i<(int)(y);++i)
#define FORE(i,x,y) for(int i=(int)(x);i<=(int)(y);++i)
#define FORD(i,x,y) for(int i=(int)(x);i>=(int)(y);--i)
#define PB push_back
#define ST first
#define ND second
typedef long long ll;
typedef pair<int,int> pii;
const int INF=2e9;
const int MAXN=2e5+7;

int n;
pii a[MAXN];
bool b[MAXN];
vector<int> find_subset(int l, int u, vector<int> w) {
    n=w.size();
    FOR(i,0,n){
        a[i]={w[i],i};
    }
    sort(a,a+n);
    ll suml=0,sumr=0;
    FOR(i,0,n){
        b[i]=true;
        suml+=a[i].ST;
        sumr+=a[n-i-1].ST;
        if(sumr>=l&&suml<=u){
            int nxt=n-1;
            for(int j=0;j<=i&&suml<l;++j){
                if(nxt>=0&&!b[nxt]){
                    b[j]=false;
                    b[nxt]=true;
                    suml-=a[j].ST;
                    suml+=a[nxt--].ST;
                }else{
                    break;
                }
            }
            if(suml>=l&&suml<=u){
                vector<int> res;
                res.reserve(i+1);
                FOR(j,0,n){
                    if(b[j])res.PB(a[j].ND);
                }
                sort(res.begin(),res.end());
                return res;
            }else{
                return vector<int>(0);
            }
        }

    }
    return 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