Submission #206817

#	Time	Username	Problem	Language	Result	Execution time	Memory
206817		vardan__02	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	68 ms	6252 KiB

molecules

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <set>
#include <map>
#include "molecules.h"
using namespace std;
#define MP make_pair
#define PB push_back
 vector<int> find_subset(int l, int u, std::vector<int> w)
 {
     vector<int> ans;
     vector<pair<int,int> > a;
     int n = w.size();
     for(int i = 0; i < n; ++i)
        a.PB(MP(w[i],i));
     sort(a.begin(), a.end());
     int left = 0, right = 0;
     long long tiv = 0;
     for(int i = 0; i < n; ++i)
     {
         while(i < n && tiv < l)
         {
             tiv += a[i].first;
             i++;
         }
         i--;
         if(tiv < l)return ans;
         if(tiv <= u)
         {
             if(u - l >= a[i].first - a[left].first)
             {
                 for(int j = left; j <= i; ++j)
                    ans.PB(a[j].second);
                 sort(ans.begin(), ans.end());
                 return ans;
             }
             else
             {
                 while(left <= i && u - l < a[i].first - a[left].first)
                 {
                     tiv -= a[left].first;
                     left++;
                 }
                 right = i;
             }
         }
         else
         {
             while(left <= i && tiv > u)
             {
                 tiv -= a[left].first;
                 left++;
             }
             while(left <= i && u - l < a[i].first - a[left].first)
             {
                 tiv -= a[left].first;
                 left++;
             }
             right = i;
         }
     }
     tiv = 0;
     for(int i = left; i <= right; ++i)
        tiv += a[i].first;
     if(tiv >= l && tiv <= u && u - l >= a[right].first - a[left].first)
     {
         for(int j = left; j <= right; ++j)
            ans.PB(a[j].second);
         sort(ans.begin(), ans.end());
         return ans;
     }
     else
        return ans;
 }

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