Submission #31093

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
31093	2017-08-08 09:40:55	TAMREF	Detecting Molecules (IOI16_molecules)	C++11	100 / 100	83 ms	4536 KiB

molecules

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
vector<int> I, ans;
vector<int> find_subset(int l, int u, std::vector<int> w) {
    int n=w.size();
    I=vector<int>(n);
    iota(I.begin(),I.end(),0);
    sort(I.begin(),I.end(),[&w](int u, int v){return w[u]<w[v];});
    long long fsum=0, rsum=0;
    for(int i=0;i<n;i++){
        fsum+=w[I[i]], rsum+=w[I[n-1-i]];
        if(fsum>u) return vector<int>(0);
        if(l<=fsum && fsum<=u){
            ans.assign(I.begin(),I.begin()+i+1);
            return ans;
        }
        if(l<=rsum && rsum<=u){
            ans.assign(I.begin()+n-1-i,I.end());
            return ans;
        }
        if(fsum<l && rsum>u){
            for(int ptr=1;ptr<n-1-i;ptr++){
                fsum+=w[I[ptr+i]]-w[I[ptr-1]];
                if(l<=fsum && fsum<=u){
                    ans.assign(I.begin()+ptr,I.begin()+ptr+i+1);
                    return ans;
                }
            }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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