Submission #781305

#	Time	Username	Problem	Language	Result	Execution time	Memory
781305		andecaandeci	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	3 ms	4000 KiB

molecules

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

// # define int long long
# define fir first
# define sec second
# define pb push_back

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

int n;
int lglo, uglo;
int weiglo[cnst];
int dp[105][1005];
string s[105][1005];

bool dpalgo(int idx, int wei) {
    // cerr << idx << " " << wei << endl;
    if(wei > uglo) return 0;
    if(lglo <= wei && wei <= uglo) return 1;
    if(idx == n+1) return 0;
    if(dp[idx][wei] != -1) return dp[idx][wei];

    bool a = dpalgo(idx+1, wei);
    bool b = 0;
    // cerr << idx << " " << wei << " " << wei+weiglo[idx] << endl;
    if(wei+weiglo[idx] <= uglo) {
        b = dpalgo(idx+1, wei+weiglo[idx]);
    }

    if(b) s[idx][wei] = s[idx+1][wei+weiglo[idx]], s[idx][wei] += '1';
    else s[idx][wei] = s[idx+1][wei], s[idx][wei] += '0';

    return dp[idx][wei] = (a|b);
}

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    int fre = 0;

    for(auto v: w) fre++, weiglo[fre] = v;
    lglo = l, uglo = u;
    n = w.size();

    // for(auto v: wei) cerr << v << " "; cerr << endl;

    memset(dp, -1, sizeof(dp));

    dpalgo(1, 0);

    // cerr << dp[1][0] << endl;

    string sans = s[1][0];
    reverse(sans.begin(), sans.end());
    // cerr << sans << endl;
    vector<int> ans;

    for(int i = 0; i<sans.size(); i++) if(sans[i] == '1') ans.pb(i+1);
    return ans;
}

/*

signed main() {
    ios_base::sync_with_stdio(false);
    // int t = 1;
    // if(mutipletestcase) cin >> t; 
    // while(t--) solve();

    int n, l, u; cin >> n >> l >> u;
    vector<int> vec(n);
    for(int i = 0; i<n; i++) cin >> vec[i];
    vector<int> ans = find_subset(l, u, vec);

    for(auto v: ans) cout << v << " ";
}
*/

Compilation message (stderr)

molecules.cpp: In function 'bool dpalgo(int, int)':
molecules.cpp:37:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   37 |     return dp[idx][wei] = (a|b);
      |            ~~~~~~~~~~~~~^~~~~~~
molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 0; i<sans.size(); i++) if(sans[i] == '1') ans.pb(i+1);
      |                    ~^~~~~~~~~~~~

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