Submission #1217602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217602		JuanJL	Detecting Molecules (IOI16_molecules)	C++20	0 / 100	0 ms	328 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i<b; i++)
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cout.tie(); cin.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> iset;

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    vector<pair<ll,ll>> o(SZ(w)); forn(i,0,SZ(w)) o[i]={w[i],i};
    sort(ALL(o));

    vector<ll> mink(SZ(w)); forn(i,0,SZ(w)){ mink[i]=o[i].fst; mink[i]+=(i-1>=0?mink[i-1]:0);}
    vector<ll> maxk(SZ(w)); for(int i = SZ(w)-1; i>=0; i--){ maxk[i]=o[i].fst; maxk[i]+=(i+1<SZ(w)?mink[i+1]:0);}


    vector<int> res = {};
    forn(i,0,SZ(w)){
        if(mink[i]<=u&&maxk[i]>=l){
            ll pres = mink[i];
            ll I = 0;
            ll J = SZ(w)-1;
            vector<int> rres;
            forn(j,0,i+1){
                if(pres>=l) break;
                pres+=o[J].fst-o[I].fst;
                rres.pb(o[J].snd);
                J--;
                I++;
                if(I==J) break;
            }
            if(pres>=l){
                forn(j,I,i+1){
                    rres.pb(o[j].snd);
                }
                res=rres;
                break;
            }
        }
    }
    return res;
}

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: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31