Submission #437846

#	Time	Username	Problem	Language	Result	Execution time	Memory
437846		Yomapeed	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	101 ms	5144 KiB

molecules

#include<bits/stdc++.h>
#include "molecules.h"
#define pi 3.141592653589793238
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999999 
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple 
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
 
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
vector<int> find_subset(int l, int u, vector<int> w){
    int i, st = 0, en = -1;
    int n = w.size();
    ll sum = 0;
    vector<int> idx;
    for(i = 0; i < n; i++){
        idx.pb(i);
    }
    sort(idx.begin(), idx.end(), [&](int a, int b){
        return w[a] < w[b];
    });
    sort(w.begin(), w.end());
    int ansl = -1, ansr = -1;
    for(i = 0; i < n; i++){
        while(sum < l && en + 1 < n){
            en++;
            sum += w[en];
        }
        if(sum >= l && sum <= u){
            ansl = st, ansr = en;
            break;
        }
        while(sum > u && st <= en){
            if(st == n){
                break;
            }
            sum -= w[st];
            st++;
        }
        if(sum >= l && sum <= u){
            ansl = st, ansr = en;
            break;
        }
    }
    if(ansl == -1){
        return {};
    }
    
    vector<int> ans;
    for(i = ansl; i <= ansr; i++){
        ans.pb(idx[i]);
    }
    return ans;
}

Compilation message (stderr)

molecules.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
molecules.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

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