Submission #575516

#	Time	Username	Problem	Language	Result	Execution time	Memory
575516		jasmin	Detecting Molecules (IOI16_molecules)	C++17	46 / 100	39 ms	808 KiB

molecules

#include<bits/stdc++.h>
#include "molecules.h"
using namespace std;

bool construct(vector<pair<int,int> >& range, vector<pair<int,int> >& a, vector<int>& sol, int left, int right){
    int n=a.size();
    int x=0;
    int i=0;

    reverse(range.begin(), range.end()); //=> aufsteigend
    reverse(a.begin(), a.end()); //=> aufsteigend
    /*for(auto e: a){
        cout << e.first << " " << e.second << "\n";
    }
    cout << "=====\n";
    for(auto e: range){
        cout << e.first << " " << e.second << "\n";
    }
    cout << ":::::::::::::::::::::::::\n";*/
    for(int j=0; j<n; j++){
        if(range[j].second<x) continue;
        if(x<range[j].first) return false;

        int l=range[j].first;
        int r=range[j].second;
        while(i<=j && x<l+(a[j].first-a[i].first)){
            //cout << j << " " << i << "\n";
            i++;
        }
        //cout << x << " " << range[j].first << " " << range[j].second << " " << a[i].first << "\n";
        sol.push_back(a[i].second);
        x+=a[i].first;
        i++;
    }
    return true;
}

vector<int> find_subset(int l, int r, vector<int> a){
    int n=a.size();
    vector<pair<int,int> > b(n);
    for(int i=0; i<n; i++){
        b[i]={a[i], i};
    }
    sort(b.begin(), b.end());
    reverse(b.begin(), b.end());

    vector<pair<int,int> > range(1, {l, r});
    for(int i=0; i<n; i++){
        pair<int,int> last=range[range.size()-1];
        range.push_back({last.first-b[i].first, last.second-b[i].first});

        for(int j=range.size()-3; j>=0; j--){
            range[j+1].second=range[j].second-b[i].first;
        }
    }

    /*for(auto e: range){
        cout << e.first << " " << e.second << "\n";
    }*/
    
    vector<int> sol;
    if(construct(range, b, sol, l, r)){
        return sol;
    }
    return {};
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, l, r;
    cin >> n >> l >> r;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    vector<int> sol=find_subset(l, r, a);
    for(auto e: sol){
        cout << e << " ";
    }
    cout << "\n";
}*/

Compilation message (stderr)

molecules.cpp: In function 'bool construct(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&, std::vector<int>&, int, int)':
molecules.cpp:25:13: warning: unused variable 'r' [-Wunused-variable]
   25 |         int r=range[j].second;
      |             ^

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