Submission #448385

#	Time	Username	Problem	Language	Result	Execution time	Memory
448385		tredsused70	Detecting Molecules (IOI16_molecules)	C++17	69 / 100	23 ms	6784 KiB

molecules

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

using namespace std;

#define accelerator ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define sc second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int nmax=100011,mod=1e9+7,inf=2000010000;
const ll infll=4000000000000000000;

vector<int> find_subset(int l,int u,vector<int> mas_)
{
    int used[100100]={0},m=0,pos,ans[100100]={0};
    vector<int> ans_;
    int n=mas_.size();
    array<int,2> mas[100100];
    ll sum=0;
    for(int i=0;i<n;i++)
        mas[i]={mas_[i],i};
    sort(mas,mas+n);
    for(int i=0;i<n;i++)
    {
        sum+=mas[i][0];
        if(sum>u)
        {
            sum-=mas[i][0];
            break;
        }
        used[mas[i][1]]=1;
        ans[m]=mas[i][1];
        m++;
        if(sum>=l)
        {
            for(int i=0;i<m;i++)
                ans_.push_back(ans[i]);
            return ans_;
        }

    }
    for(int i=m-1;i>=0;i--)
    {
        if(used[mas[n-m+i][1]])
            continue;
        used[mas[i][1]]=0;
        used[mas[n-m+i][1]]=1;
        sum-=mas[i][0];
        sum+=mas[n-m+i][0];
        ans[i]=mas[n-m+i][1];
        if(sum>=l)
        {
            for(int i=0;i<m;i++)
                ans_.push_back(ans[i]);
            return ans_;
        }
    }
    return {};
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:20:30: warning: unused variable 'pos' [-Wunused-variable]
   20 |     int used[100100]={0},m=0,pos,ans[100100]={0};
      |                              ^~~

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