Submission #500418

#	Time	Username	Problem	Language	Result	Execution time	Memory
500418		Marceantasy	Detecting Molecules (IOI16_molecules)	C++17	31 / 100	496 ms	65540 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"
 
using namespace std; 
 
#define ll long long
 
const int mxN = 2e5; 
map<pair<ll, int>, bool> mp; 
 
vector<int> solve(ll pts, int pos, bitset<200000>& bs, int l, int u, vector<int>& w){
    vector<int> ans; 
    int n = w.size(); 
    if(pos == n){
        if(pts >= l && pts <= u){
            for(int i = 0; i<bs.size(); ++i){
                if(bs[i]){
                    ans.push_back(i); 
                }
            }
        }
        return ans;
    }
    if(pts > u || mp[{pts, pos}] || pos > n){
        return ans;
    }
    mp[{pts, pos}] = 1; 
    if(pts >= l && pts <= u){
        vector<int> ans; 
        for(int i = 0; i<bs.size(); ++i){
            if(bs[i]){
                ans.push_back(i);  
            }
        }
        return ans; 
    }
    bs[pos] = 1; 
    vector<int> intento1 = solve(pts+w[pos], pos+1, bs, l, u, w); 
    if(intento1.size()){
        return intento1; 
    }else{
        bs[pos] = 0; 
        vector<int> intento2 = solve(pts, pos+1, bs, l, u, w);
        if(intento2.size()){
            return intento2; 
        }else{
            return ans; 
        }
    }
    return ans;
}
 
vector<int> find_subset(int l, int u, vector<int> w){
    bitset<200000> bt; 
    vector<int> ans = solve(0, 0, bt, l, u, w); 
    return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> solve(long long int, int, std::bitset<200000>&, int, int, std::vector<int>&)':
molecules.cpp:16:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
   16 |             for(int i = 0; i<bs.size(); ++i){
      |                            ~^~~~~~~~~~
molecules.cpp:30:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int i = 0; i<bs.size(); ++i){
      |                        ~^~~~~~~~~~

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