Submission #416019

#	Time	Username	Problem	Language	Result	Execution time	Memory
416019		AugustinasJucas	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	75 ms	10116 KiB

molecules

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

vector<int> find_subset(int l, int r, vector<int> w) {
    vector<pair<int, int> > deltas;
    vector<pair<int, int> > mas;
    for(int i = 0; i < w.size(); i++){
        mas.push_back({w[i], i});
    }
    sort(mas.begin(), mas.end());
    long long sm = 0;
    for(auto x : mas){
        deltas.push_back({x.first - mas[0].first, x.second});
        sm += x.first - mas[0].first;
    }
    sort(deltas.begin(), deltas.end());
    vector<long long> pref;
    for(auto x : deltas){
        pref.push_back((pref.size() ? pref.back() : 0ll) + x.first);
    }
//    cout << "skaiciai: "; for(auto x : deltas) cout << x.first << " "; 
//    cout <<endl;
    for(int i = 1; i <= (int) w.size(); i++){
        long long L = l - 1ll *  i * mas[0].first;
        long long R = r - 1ll * i * mas[0].first;

        // reikia i skaiciu, kad ju suma butu intervale [L; R];
        // pref[j] - pref[i-j]
//        cout << "reikia " << i << " skaiciu, kad ju suma butu intervale " << L << "; " << R << endl;
        if(pref[i-1] > R || pref[(int)pref.size() - 1] - ((int)pref.size()-1-i < 0 ? 0ll : pref[(int)pref.size()-1-i]) < L) continue;
  //      cout << "ce! " << endl;
        deque<int> ret1;
        vector<int> ret;
        long long cur = 0;
        for(int j = 0; j < i; j++){
            ret1.push_back(deltas[j].second);
            cur += deltas[j].first;
        }
//        cout << "CUR = " << cur << endl;
        if(L <= cur && cur <= R){
            for(auto x : ret1) ret.push_back(x);
            return ret;
        }
        for(int j = i; j < w.size(); j++){
            ret1.push_back(deltas[j].second);
            ret1.pop_front();
            cur -= deltas[j-i].first;
            cur += deltas[j].first;
            if(L <= cur && cur <= R){
                for(auto x : ret1) ret.push_back(x);
                return ret;
            }
            if(L <= cur && cur <= R){
                return ret;
            }
        }
        return {};
    }
    return {};
    
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:8:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for(int i = 0; i < w.size(); i++){
      |                    ~~^~~~~~~~~~
molecules.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int j = i; j < w.size(); j++){
      |                        ~~^~~~~~~~~~

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