Submission #789886

#	Time	Username	Problem	Language	Result	Execution time	Memory
789886		Malix	Detecting Molecules (IOI16_molecules)	C++14	9 / 100	1 ms	212 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> find_subset(int l, int u, std::vector<int> w) {

    int arrSize = w.size();
    int gap = u - l;
    vector<int> answer;
    vector<int> answertemp;

    vector<int> temp = w;
    sort(temp.begin(), temp.end());


        if(arrSize == 1){
        if(w[0]<=u && w[0]>=l){
            answer.push_back(0);
            return answer;
        }
            return std::vector<int>(0);
        }

        if(temp[0] == temp[arrSize-1]){
            int modval = u%w[0];
            if(modval<=gap){
                int termcount = (u-modval)/w[0];
                if(arrSize>=termcount){
                    for(int i = 0; i < termcount; i++){
                        answer.push_back(i);
                    }
                    return answer;
                }
            }
            return std::vector<int>(0);
        }
        
        
        
        if(temp[arrSize-1]-temp[0]==1){
            int val, k2;
            int k1 = -1;
            int it = find(temp.begin(), temp.end(), temp[arrSize-1])-temp.begin();
            int smallcount = it;
            int largecount = arrSize-it;
            for(int i = 0; i < smallcount; i++){
                for(int j = 0; j < largecount; j++){
                    val = temp[0]*i+temp[arrSize-1]*j;
                    if(val>=l && val<=u){
                        k1 = i;
                        k2 = j;
                        break;
                    }
                }
                if(k1==i){
                    break;
                }
                
            }
            int m = 0;
            if(k1 == -1 && !k2){
                return std::vector<int>(0);
            }
            while(k1 || k2){
                if(w[m]==temp[0] && k1){
                    answer.push_back(m);
                    k1--;
                }
                else if(w[m]==temp[arrSize-1] && k2){
                    answer.push_back(m);
                    k2--;
                }
                m++;
            }
            
        }
        
        /*
        if(temp[arrSize-1]-temp[0]==1){
            vector<vector<int> > elements(2);
            for(int i = 0; i < arrSize; i++){
                if(w[i]==temp[0]){
                    elements[0].push_back(i);
                }
                else{
                    elements[1].push_back(i);
                }
            }

            int right = 1;
            int left = 0;
            int sum = temp[0];
            answertemp.push_back(0);

            while(sum<l){
                sum += temp[right];
                answertemp.push_back(right);
                right++;
                if(right >= arrSize){
                    return std::vector<int>(0);
                }
                while(sum>u){
                    sum -= temp[left];
                    left++;
                    answertemp.erase(answertemp.begin()+0);
                }
            }
            while(!(sum>=l && sum<=u)){
                sum -= temp[left];
                left++;
                answertemp.erase(answertemp.begin()+0);
                sum += temp[right];
                answertemp.push_back(right);
                right++;
                if(right >= arrSize){
                    return std::vector<int>(0);
                }
     
            int asize = answertemp.size();
            int c1 = 0;
            int c2 = 0;
            answer.clear();
            for(int i = 0; i < asize; i++){
                if(temp[answertemp[i]]==temp[0]){
                    answer.push_back(elements[0][c1]);
                    c1++;
                }
                else{
                    answer.push_back(elements[1][c2]);
                    c2++;
                }
            }
            return answer;


        }




        if(temp[arrSize-1] - temp[0] == 1){
            vector<int> smallarr;
            vector<int> largearr;
            int largeSize = 0;
            for(int i = 0; i < arrSize; i++){
                if(m[i]==temp[n-1]){
                    largearr.push_back(i);
                    largeSize++;
                }
                else{
                    smallarr.push_back(i);
                    smallSize++;
                }
            }

            int mult = temp[0]*temp[n-1];
            int modval = u%mult;
            int reps = u/mult;

            int smallmod = modval%temp[0];
            int largemod = modval%temp[arrSize-1];
            int smalldiv = modval/temp[0];
            int largediv = modval/temp[arrSize-1];

            if(smallmod==0 && smalldiv>=smallSize){
                smallSize -= smalldiv;
                for(int i = 0; i < smalldiv; i++){
                    answer.push_back(smallarr[i]);
                    smallarr.erase(i);
                    smallSize--;
                }






            }
            else if(largemod==0 && largediv>=largeSize){
                largeSize -= largediv;
                for(int i = 0; i < largediv; i++){
                    answer.push_back(largearr[i]);
                    largearr.erase(i);
                }

            }


        }
        */





    return std::vector<int>(0);
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:61:13: warning: 'k2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |             if(k1 == -1 && !k2){
      |             ^~

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