oj.uz

Submission #307257

# Submission time Handle Problem Language Result Execution time Memory
307257 2020-09-27T13:31:41 Z mihai145 Detecting Molecules (IOI16_molecules) C++14
0 / 100
 8 ms 3328 KB 
#include "molecules.h"
#include <vector>
#include <bitset>

const int DIM = 8388608; ///2^23
std::bitset <DIM> s;

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    std::vector <int> ans;

    s[0] = 1;

    for(auto it : w)
        s |= (s << it);

    int p = -1;
    for(int pos = l; pos <= u; pos++)
        if(s[pos] == 1)
            {
                p = pos;
                break;
            }

    if(p == -1)
        return ans;

    int pointerW = (int)w.size() - 1;

    while(p > 0)
        {
            while(p - w[pointerW] < 0 || s[p - w[pointerW]] != 1)
                pointerW--;

            ans.push_back(pointerW);
            p -= w[pointerW];
        }

    return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3328 KB OK (n = 1, answer = NO)
2 Correct 3 ms 3328 KB OK (n = 1, answer = NO)
3 Correct 3 ms 3328 KB OK (n = 1, answer = YES)
4 Incorrect 5 ms 3328 KB item #1 is taken twice
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3328 KB item #11 is taken twice
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3328 KB OK (n = 1, answer = NO)
2 Correct 3 ms 3328 KB OK (n = 1, answer = NO)
3 Correct 3 ms 3328 KB OK (n = 1, answer = YES)
4 Incorrect 5 ms 3328 KB item #1 is taken twice
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3328 KB OK (n = 1, answer = NO)
2 Correct 3 ms 3328 KB OK (n = 1, answer = NO)
3 Correct 3 ms 3328 KB OK (n = 1, answer = YES)
4 Incorrect 5 ms 3328 KB item #1 is taken twice
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3328 KB OK (n = 1, answer = NO)
2 Correct 3 ms 3328 KB OK (n = 1, answer = NO)
3 Correct 3 ms 3328 KB OK (n = 1, answer = YES)
4 Incorrect 5 ms 3328 KB item #1 is taken twice
5 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3328 KB OK (n = 1, answer = NO)
2 Correct 3 ms 3328 KB OK (n = 1, answer = NO)
3 Correct 3 ms 3328 KB OK (n = 1, answer = YES)
4 Incorrect 5 ms 3328 KB item #1 is taken twice
5 Halted 0 ms 0 KB -