Submission #1080732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080732		ALeonidou	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	1 ms	432 KiB

molecules

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

using namespace std;

#define ll int
#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;
}

vi find_subset(int l, int r, vi cc) {
    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[c[i].S] = i;
    }
    
    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 vi();
    }
    if (s > r){
        rem(p);
        p--;
    }
    // dbg(p);
    ll m = min(p, n-p-2);
    p = 0;
    // dbg2(s,m);
    while (p <= m && s < l){
        rem(p);
        add(n-p-1);
        p++;
    }
    if (s < l) return vi();

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

    return ans;
}

/*

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: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31