Submission #781289

#	Time	Username	Problem	Language	Result	Execution time	Memory
781289		devariaota	Detecting Molecules (IOI16_molecules)	C++17	Compilation error	0 ms	0 KiB

molecules

#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] = (dpalgo(idx+1, wei)|dpalgo(idx+1, wei+weiglo[idx]));
}

vector<int> find_subset(int l, int u, vector<int> wei) {
    int fre = 0;

    for(auto v: wei) fre++, weiglo[fre] = v;
    lglo = l, uglo = u;
    n = wei.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(long long int, long long int)':
molecules.cpp:36:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   36 |     return dp[idx][wei] = (dpalgo(idx+1, wei)|dpalgo(idx+1, wei+weiglo[idx]));
      |            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
molecules.cpp:26:10: warning: unused variable 'a' [-Wunused-variable]
   26 |     bool a = dpalgo(idx+1, wei);
      |          ^
molecules.cpp: In function 'std::vector<long long int> find_subset(long long int, long long int, std::vector<long long int>)':
molecules.cpp:59:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i<sans.size(); i++) if(sans[i] == '1') ans.pb(i+1);
      |                    ~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccUFrsOK.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccLOyfnM.o:molecules.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccUFrsOK.o: in function `main':
grader.cpp:(.text.startup+0x18d): undefined reference to `find_subset(int, int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status