Submission #1080759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080759		ALeonidou	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	76 ms	16720 KiB

molecules

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

using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define sz(x) (ll)x.size()

typedef vector <ll> vi;
typedef pair<ll,ll> ii;
typedef vector <ii> vii;

#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

void printVct(vi &v){
    for (ll i =0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

#define ins insert

ll s;
set <ll> st;
vii c;

void add(ll idx){
    st.ins(idx);
    s += c[idx].F;
}

void rem(ll idx){
    st.erase(idx);
    s -= c[idx].F;
}

vector <int> find_subset(int L, int R, vector <int> cc) {
    ll l = L, r = R;
    c.resize(sz(cc));
    vi mp(sz(c));
    for (ll i =0; i<sz(c); i++){
        c[i] = ii(cc[i], i);
    }
    sort(c.begin(), c.end());
    for (ll i =0; i<sz(c); i++){
        mp[i] = c[i].S;
    }

    ll n = sz(c), p = 0; s = 0;
    while (p < n && s < l){
        add(p);
        p++;
    }
    p--;
    if (s < l){     //impossible to reach l
        return vector <int>();
    }
    if (s > r){
        rem(p);
        p--;
    }
    ll m = min(p, n-p-2);
    p = 0;
    while (p <= m && s < l){
        rem(p);
        add(n-p-1);
        p++;
    }
    if (s < l) return vector <int>();

    vector<int> ans;
    for (set <ll> :: iterator it = st.begin(); it != st.end(); it++){
        ans.pb(mp[*it]);
    }
    sort(ans.begin(), ans.end());

    return ans;
}

/*

5 16 22
10 13 14 16 12 

4 15 17
6 8 8 7

10 50 51
8 9 9 8 9 8 9 8 8 8
*/

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