Submission #1235769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235769		dssfsuper2	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	52 ms	12856 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll> mapping;
vector<ll> reversem;
vector<int> find_subset(int l, int u, vector<int> w) {
    vector<pair<int, int>> things;
    mapping.resize(w.size());
    for(int i = 0;i<w.size();i++){
        things.push_back({w[i], i});
    }
    sort(things.begin(), things.end());
    for(int i = 0;i<w.size();i++){
        reversem.push_back(things[i].second);
        mapping[things[i].second]=i;
    }
    sort(w.begin(), w.end());
    vector<ll> prs, prss;
    ll a = 0;
    vector<int> anss;
    for(ll i = 0;i<w.size();i++){
        a+=w[i];
        prs.push_back(a);
        anss.push_back(reversem[i]);
        if(a>=l && a<=u)return anss;
    }
    a=0;
    anss.clear();
    for(ll i = w.size()-1;i>=0;i--){
        a+=w[i];
        prss.push_back(a);
        anss.push_back(reversem[i]);
        if(a>=l && a<=u)return anss;
    }
    int res = -1;
    for(int i = 0;i<w.size();i++){
        if(prs[i]<=u && prss[i]>=l)res=i+1;
    }
    if(res==-1)return {};
    if (prs[res-1]>=l && prs[res-1]<=u){
        vector<int> ans;
        for(int i = 0;i<res;i++){
            ans.push_back(reversem[i]);
        }
        return ans;
    }
    if (prss[res-1]>=l && prss[res-1]<=u){
        vector<int> ans;
        for(int i = w.size()-1;i>=w.size()-res;i--){
            ans.push_back(reversem[i]);
        }
        return ans;
    }
    
    deque<int> ans;
    ll tot=0;
    for(ll i = 0;i<res;i++){
        ans.push_back(reversem[i]);
        tot+=w[i];
    }
    int end = w.size()-1;
    while(tot<l ){
        tot-=w[mapping[ans.front()]];
        tot+=w[end];
        ans.pop_front();
        ans.push_back(reversem[end]);
        end--;
    }
    vector<int> ansv;
    for(auto thing:ans)ansv.push_back(thing);
    return ansv;
}

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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