Submission #1136935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136935		owoovo	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	36 ms	8264 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>
#define ll long long 
#define F first 
#define S second 
using namespace std;

int n;
ll l,u,pre[200010],erp[200010];
pair<ll,int> w[200010];
vector<int> find_subset(int L, int U, vector<int> W) {
    int n=W.size(),u=U,l=L;
    for(int i=1;i<=n;i++){
        w[i]={W[i-1],i-1};
    }
    sort(&w[1],&w[n+1]);
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+w[i].F;
    }
    for(int i=n;i>=1;i--){
        erp[i]=erp[i+1]+w[i].F;
    }
    vector<int> ans;
    for(int i=1;i<=n;i++){
        if(pre[i]>u||erp[n-i+1]<l)continue;
        int j=i;
        while(pre[j-1]+erp[n-(i-j+1)+1]<l){
            j--;
        }
        for(int k=1;k<j;k++){
            ans.push_back(w[k].S);
        }
        for(int k=n-i+j+1;k<=n;k++){
            ans.push_back(w[k].S);
        }
        for(int k=j;k<=n-i+j;k++){
            ll sum=pre[j-1]+erp[n-i+j+1]+w[k].F;
            if(sum>=l&&sum<=u){
                ans.push_back(w[k].S);
                break;
            }
        }
        break;
    }

    return ans;
}

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