Submission #165049

#	Time	Username	Problem	Language	Result	Execution time	Memory
165049		Sparky_09	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	3 ms	424 KiB

molecules

#include<bits/stdc++.h>
#ifdef LOCAL_DEFINE
#include<conio.h>
#endif
using namespace std;
void io();
void end();

vector<int> find_subset(int l, int u, vector<int> v){
    int n = v.size();
    vector<pair<int, int>> p(n);
    vector<int> ans(0), pref(n+1, 0);

    for(int i = 0; i < n; i++){
        p[i] = {v[i], i};
        pref[i+1]=pref[i]+v[i];
        if(v[i]>=l and v[i]<=u){ ans.push_back(i); return ans; }
    }

    int ll = -1, r = -1;
    sort(p.begin(), p.end());
    for(int i = 0, j = 1; j<=n and i!=j;){
        if((pref[j]-pref[i])>=l and (pref[j]-pref[i])<=u){ ll = i; r = j-1; break; }
        if((pref[j]-pref[i])>u) i++;
        else if((pref[j]-pref[i])<l) j++;
        
    }

    if(ll==-1) for(int i = n-1, j = n; i>=0;){
        if((pref[j]-pref[i])>=l and (pref[j]-pref[i])<=u){ ll = i; r = j-1; break; }
        if((pref[j]-pref[i])>u){ j--; if(i==j) i--; }
        else if((pref[j]-pref[i])<l) i--;
        
    }
    
    if(ll!=-1) for(int i = ll; i <= r; i++) ans.push_back(p[i].second);

    return ans;
}
/*
int main(){
    io();
    int l, u, n;
    cin >> l >> u >> n;
    vector<int> v(n);
    for(int& i: v) cin >> i;
    vector<int> z = find_subset(l, u, v);
    for(auto i: z) cout << i << ' ';
    end();
}
*/

void io(){
#ifdef LOCAL_DEFINE
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen("input.txt", "rt", stdin);
#endif
}

void end(){	
#ifdef LOCAL_DEFINE
	cerr << "\nTime Elapsed: " << 1.0 * clock()/CLOCKS_PER_SEC << " s.\n";
	getch();
#endif
}

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