Submission #730794

#	Time	Username	Problem	Language	Result	Execution time	Memory
730794		ETheBest3	Detecting Molecules (IOI16_molecules)	C++14	19 / 100	1 ms	312 KiB

molecules

#include<bits/stdc++.h>
//#include "molecules.h"
#define lli int
using namespace std;
vector<lli> ans, otg;
vector<pair<lli, lli>> W;
lli N;
bool used[200005];
void to_otg(){
    for(lli i=0; i<ans.size(); i++){
        otg.push_back(W[ans[i]].second);
    }
    return;
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    for(lli i=0; i<w.size(); i++)W.push_back({w[i], i});
    sort(W.begin(), W.end());
    N=W.size();
    lli p1=0, p2=0, sum=0;
    while(sum<=l and p2<N){
        if(sum+W[p2].first>l)break;
        sum+=W[p2].first;
        ans.push_back(W[p2].second);
        p2++;
    }
    if(sum==l){
        return ans;
    }
    if(p2<N and sum+W[p2].first>=l and sum+W[p2].first<=u){
        ans.push_back(p2);
        return ans;
    }
    if(ans.size()==0)return vector<int>(0);
    while(p2<N){
        sum+=W[p2].first-w[ans[p1%ans.size()]];
        ans[p1%ans.size()]=W[p2].second;
        if(sum>=l and sum<=u)break;
        p1++;
        p2++;
    }
    if(sum<l or sum>u)return vector<int>(0);
    return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'void to_otg()':
molecules.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(lli i=0; i<ans.size(); i++){
      |                  ~^~~~~~~~~~~
molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(lli i=0; i<w.size(); i++)W.push_back({w[i], i});
      |                  ~^~~~~~~~~

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