Submission #524265

#	Time	Username	Problem	Language	Result	Execution time	Memory
524265		cqtshadow	Detecting Molecules (IOI16_molecules)	C++14	46 / 100	29 ms	588 KiB

molecules

#include <bits/stdc++.h>
#define MASK(x) (1LL << x)
#define GETBIT(mask, x) ((mask >> (x))&1)
#define ONBIT(mask, x) (mask | (1LL << (x)))
#define Each(type, i, a, b) for(type i = (a) ; i <= (b) ; ++i)
#define REach(type, i, a, b) for(type i = (a) ; i >= (b) ; --i)
using namespace std;

typedef long long ll;

const int N = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 2e9;
const double eps = 1e-9;
const ll oo = 4e18;

template<class X> bool maximize(X &x, X y) {return (x + eps < y ? x = y, true : false);}
template<class X> bool minimize(X &x, X y) {return (x > y + eps ? x = y, true : false);}

void add(int &x, int y) {x += y; if(x >= MOD) x -= MOD;}
void sub(int &x, int y) {x -= y; if(x < 0) x += MOD;}
int radd(int x, int y) {add(x, y); return x;}
int rsub(int x, int y) {sub(x, y); return x;}

string to2(int val) {bitset<10> temp(val); return temp.to_string();}

int n;

namespace SUB1 {
    vector<int> solve(int l, int u, vector<int> w) {
        vector<int> result(0);
        int sum = 0;
        while(result.size() < n && sum < l) {
            result.push_back(result.size());
            sum += w[0];
        }
        if(sum > u || sum < l) return vector<int>(0);
        return result;
    }
}

namespace SUB4 {
    bool f[10003];
    int id[10003];

    vector<int> solve(int l, int u, vector<int> w) {
        vector<int> result;
        f[0] = 1;
        Each(int, i, 0, n - 1) {
            REach(int, wei, u, w[i])
                if(f[wei - w[i]] && !f[wei]) {
                    f[wei] = 1;
                    id[wei] = i;
                    if(l <= wei && wei <= u) {
                        int cur = wei;
                        while(cur > 0) {
                            result.push_back(id[cur]);
                            cur -= w[id[cur]];
                        }
                        return result;
                    }
                }
        }
        return vector<int>(0);
    }
}

vector<int> find_subset(int l, int u, vector<int> w) {
    n = w.size();
    int wmax = -1;
    bool isequal = true; int ele = w[0];

    for(int x : w) {
        maximize(wmax, x);
        isequal &= (ele == x);
    }

    if(n <= 100 && wmax <= 100 && l <= 1000 && isequal)
        return SUB1::solve(l, u, w);

    if(n <= 10000 && l <= 10000)
        return SUB4::solve(l, u, w);
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> SUB1::solve(int, int, std::vector<int>)':
molecules.cpp:33:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |         while(result.size() < n && sum < l) {
      |               ~~~~~~~~~~~~~~^~~
molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^

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