Submission #1250506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250506		ammaka	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	38 ms	8364 KiB

molecules

//#include <GOD>
//kole shahr khakestary , bala sar man ranginkamon
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define pb push_back
#define len length	
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define freo freopen("guard.out","w",stdout)
#define frei freopen("guard.in","r",stdin)

const ll inf=1e18+10;
const ll mod=1e9+7;
const ll maxn=(2e5)+10,maxm=1e5+10,sq=310+10,maxa=(1<<maxn),mlg=32;


ll ss[maxn],ps[maxn];

vector<int> find_subset(int l, int u, vector<int> w){
    // frei;
    // freo;
	// FAST_IO;
    // ll l=(long long)l;

    ll n=w.size();
    vector <pair<ll,ll>> srt_w;
    for(int i=0;i<n;i++){
        srt_w.pb({(long long)w[i],i});
    }
    sort(srt_w.begin(),srt_w.end());
    ll ind;
    ll mn = 2147483648ll;
    vector <int> ans;
    ans.clear();
    // cout<<mn<<endl;
    if(l>u){
        return ans;
    }
    for(int i=1;i<=n;i++){
        ps[i]=ps[i-1]+srt_w[i-1].first;
        if(srt_w[i-1].first<mn){
            mn=srt_w[i-1].first;
            ind=srt_w[i-1].second;
        }
    }
    for(int i=n;i>=1;i--){
        ss[i]=ss[i+1]+srt_w[i-1].first;
    }
    if(mn<=u&&ps[n]>=l){

        if(mn>=l){

    // cout<<mn<<' '<<u<<' '<<l<<' '<<ps[n]<<endl;
            ans.pb(ind);
            // cout<<ind<<endl;
            return ans;
        }else if(ps[n]<=u){
            for(int i=0;i<n;i++){
                ans.pb(i);
            }
            return ans;
        }else{
            for(int k=1;k<=n;k++){
                if(ps[k]>=l&&ps[k]<=u){
                    for(int i=0;i<k;i++){
                        ans.pb(srt_w[i].second);
                    }
                    return ans;
                }else if(ss[n-k+1]>=l&&ss[n-k+1]<=u){
                    for(int i=n-1;i>=n-k;i--){
                        ans.pb(srt_w[i].second);
                    }
                    return ans;
                }else if(ps[k]<l&&ss[n-k+1]>u){
                    for(int i=1;i<=n-k+1;i++){
                        if(ps[i+k-1]-ps[i-1]>=l){
                            for(int j=i;j<=i+k-1;j++){
                                ans.pb(srt_w[j-1].second);
                            }
                            return ans;
                        }
                    }
                }
            }
            return ans;
        }
    }else{
        return ans;
    }
}

// int main(){
//     vector <int> ans;
//     ans=find_subset(10, 20, {15, 17, 16, 18});
//     cout<<ans.size()<<endl;
//     for(int i=0;i<ans.size();i++){
//         cout<<ans[i]<<' ';
//     }cout<<endl;
// }

Compilation message (stderr)

molecules.cpp:15:53: warning: left shift count >= width of type [-Wshift-count-overflow]
   15 | const ll maxn=(2e5)+10,maxm=1e5+10,sq=310+10,maxa=(1<<maxn),mlg=32;
      |                                                    ~^~~~~~
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