Submission #787371

#	Time	Username	Problem	Language	Result	Execution time	Memory
787371		fatemetmhr	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	40 ms	6964 KiB

molecules

//  ~ Be Name Khoda ~  //

#include "molecules.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

vector <pair<ll, int>> w;
ll ps[maxn5];
bool mark[maxn5];

std::vector<int> find_subset(int l, int u, std::vector<int> W) {
    int n = W.size();
    for(int i = 0; i < n; i++)
        w.pb({W[i], i});
    sort(all(w));
    ps[0] = w[0].fi;
    for(int i = 1; i < n; i++)
        ps[i] = w[i].fi + ps[i - 1];
    for(int len = 1; len <= n; len++){
        //cout << len << ' ' << l << ' ' << u << ' ' << ps[len - 1] << ' ' << ps[n - 1] - (len == n ? 0 : ps[n - len - 1]) << endl;
        if(ps[len - 1] <= u && ps[n - 1] - (len == n ? 0 : ps[n - len - 1]) >= l){
            ll sum = 0;
            for(int i = 0; i < len; i++){
                mark[i] = true;
                sum += w[i].fi;
            }
            int pt = 0, ind = n - 1;
            while(sum < l){
                //cout << len << ' ' << sum << ' ' << pt << ' ' << ind << endl;
                mark[pt] = false;
                sum += w[ind].fi - w[pt].fi;
                mark[ind] = true;
                pt++;
                ind--;
            }
            vector <int> ans;
            for(int i = 0; i < n;i ++) if(mark[i])
                ans.pb(w[i].se);
            return ans;
        }
    }
    vector <int> ans;
    ans.clear();
    return ans;
}

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