oj.uz

Submission #410956

# Submission time Handle Problem Language Result Execution time Memory
410956 2021-05-24T01:11:27 Z Marceantasy Detecting Molecules (IOI16_molecules) C++17
31 / 100
 40 ms 65540 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB OK (n = 1, answer = NO)
2 Correct 1 ms 204 KB OK (n = 1, answer = NO)
3 Correct 2 ms 288 KB OK (n = 1, answer = YES)
4 Correct 2 ms 296 KB OK (n = 2, answer = YES)
5 Correct 1 ms 292 KB OK (n = 2, answer = YES)
6 Correct 2 ms 204 KB OK (n = 3, answer = YES)
7 Correct 1 ms 204 KB OK (n = 3, answer = YES)
8 Correct 2 ms 204 KB OK (n = 3, answer = YES)
9 Correct 2 ms 204 KB OK (n = 3, answer = YES)
10 Correct 1 ms 204 KB OK (n = 3, answer = YES)
11 Correct 2 ms 240 KB OK (n = 3, answer = YES)
12 Correct 1 ms 204 KB OK (n = 3, answer = YES)
13 Correct 1 ms 204 KB OK (n = 3, answer = NO)
14 Correct 1 ms 204 KB OK (n = 3, answer = YES)
15 Correct 2 ms 204 KB OK (n = 3, answer = YES)
16 Correct 1 ms 204 KB OK (n = 3, answer = NO)
17 Correct 1 ms 204 KB OK (n = 3, answer = NO)
18 Correct 1 ms 332 KB OK (n = 100, answer = NO)
19 Correct 2 ms 332 KB OK (n = 100, answer = YES)

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB OK (n = 12, answer = YES)
2 Correct 2 ms 204 KB OK (n = 12, answer = YES)
3 Correct 1 ms 204 KB OK (n = 12, answer = NO)
4 Correct 1 ms 204 KB OK (n = 12, answer = NO)
5 Correct 2 ms 204 KB OK (n = 12, answer = YES)
6 Correct 2 ms 332 KB OK (n = 12, answer = YES)
7 Correct 1 ms 288 KB OK (n = 12, answer = YES)
8 Correct 2 ms 204 KB OK (n = 12, answer = YES)
9 Correct 2 ms 204 KB OK (n = 6, answer = YES)
10 Correct 2 ms 292 KB OK (n = 12, answer = YES)
11 Correct 4 ms 716 KB OK (n = 100, answer = NO)
12 Correct 2 ms 332 KB OK (n = 100, answer = YES)
13 Correct 5 ms 844 KB OK (n = 100, answer = NO)
14 Correct 3 ms 460 KB OK (n = 100, answer = YES)
15 Correct 2 ms 332 KB OK (n = 100, answer = YES)
16 Correct 10 ms 1332 KB OK (n = 100, answer = YES)
17 Correct 4 ms 588 KB OK (n = 100, answer = YES)

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB OK (n = 1, answer = NO)
2 Correct 1 ms 204 KB OK (n = 1, answer = NO)
3 Correct 2 ms 288 KB OK (n = 1, answer = YES)
4 Correct 2 ms 296 KB OK (n = 2, answer = YES)
5 Correct 1 ms 292 KB OK (n = 2, answer = YES)
6 Correct 2 ms 204 KB OK (n = 3, answer = YES)
7 Correct 1 ms 204 KB OK (n = 3, answer = YES)
8 Correct 2 ms 204 KB OK (n = 3, answer = YES)
9 Correct 2 ms 204 KB OK (n = 3, answer = YES)
10 Correct 1 ms 204 KB OK (n = 3, answer = YES)
11 Correct 2 ms 240 KB OK (n = 3, answer = YES)
12 Correct 1 ms 204 KB OK (n = 3, answer = YES)
13 Correct 1 ms 204 KB OK (n = 3, answer = NO)
14 Correct 1 ms 204 KB OK (n = 3, answer = YES)
15 Correct 2 ms 204 KB OK (n = 3, answer = YES)
16 Correct 1 ms 204 KB OK (n = 3, answer = NO)
17 Correct 1 ms 204 KB OK (n = 3, answer = NO)
18 Correct 1 ms 332 KB OK (n = 100, answer = NO)
19 Correct 2 ms 332 KB OK (n = 100, answer = YES)
20 Correct 2 ms 204 KB OK (n = 12, answer = YES)
21 Correct 2 ms 204 KB OK (n = 12, answer = YES)
22 Correct 1 ms 204 KB OK (n = 12, answer = NO)
23 Correct 1 ms 204 KB OK (n = 12, answer = NO)
24 Correct 2 ms 204 KB OK (n = 12, answer = YES)
25 Correct 2 ms 332 KB OK (n = 12, answer = YES)
26 Correct 1 ms 288 KB OK (n = 12, answer = YES)
27 Correct 2 ms 204 KB OK (n = 12, answer = YES)
28 Correct 2 ms 204 KB OK (n = 6, answer = YES)
29 Correct 2 ms 292 KB OK (n = 12, answer = YES)
30 Correct 4 ms 716 KB OK (n = 100, answer = NO)
31 Correct 2 ms 332 KB OK (n = 100, answer = YES)
32 Correct 5 ms 844 KB OK (n = 100, answer = NO)
33 Correct 3 ms 460 KB OK (n = 100, answer = YES)
34 Correct 2 ms 332 KB OK (n = 100, answer = YES)
35 Correct 10 ms 1332 KB OK (n = 100, answer = YES)
36 Correct 4 ms 588 KB OK (n = 100, answer = YES)
37 Correct 1 ms 204 KB OK (n = 28, answer = YES)
38 Correct 4 ms 588 KB OK (n = 27, answer = YES)
39 Correct 18 ms 2252 KB OK (n = 90, answer = YES)
40 Correct 2 ms 204 KB OK (n = 100, answer = YES)
41 Correct 2 ms 332 KB OK (n = 100, answer = YES)
42 Correct 2 ms 204 KB OK (n = 10, answer = YES)
43 Correct 2 ms 332 KB OK (n = 100, answer = YES)
44 Correct 4 ms 460 KB OK (n = 100, answer = YES)
45 Correct 7 ms 988 KB OK (n = 100, answer = YES)
46 Correct 2 ms 332 KB OK (n = 100, answer = YES)
47 Correct 26 ms 3076 KB OK (n = 100, answer = NO)
48 Correct 1 ms 332 KB OK (n = 100, answer = NO)
49 Correct 3 ms 588 KB OK (n = 100, answer = NO)
50 Correct 2 ms 332 KB OK (n = 100, answer = YES)
51 Correct 2 ms 332 KB OK (n = 100, answer = YES)
52 Correct 4 ms 672 KB OK (n = 100, answer = YES)
53 Correct 2 ms 204 KB OK (n = 100, answer = YES)
54 Correct 2 ms 332 KB OK (n = 100, answer = YES)

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB OK (n = 1, answer = NO)
2 Correct 1 ms 204 KB OK (n = 1, answer = NO)
3 Correct 2 ms 288 KB OK (n = 1, answer = YES)
4 Correct 2 ms 296 KB OK (n = 2, answer = YES)
5 Correct 1 ms 292 KB OK (n = 2, answer = YES)
6 Correct 2 ms 204 KB OK (n = 3, answer = YES)
7 Correct 1 ms 204 KB OK (n = 3, answer = YES)
8 Correct 2 ms 204 KB OK (n = 3, answer = YES)
9 Correct 2 ms 204 KB OK (n = 3, answer = YES)
10 Correct 1 ms 204 KB OK (n = 3, answer = YES)
11 Correct 2 ms 240 KB OK (n = 3, answer = YES)
12 Correct 1 ms 204 KB OK (n = 3, answer = YES)
13 Correct 1 ms 204 KB OK (n = 3, answer = NO)
14 Correct 1 ms 204 KB OK (n = 3, answer = YES)
15 Correct 2 ms 204 KB OK (n = 3, answer = YES)
16 Correct 1 ms 204 KB OK (n = 3, answer = NO)
17 Correct 1 ms 204 KB OK (n = 3, answer = NO)
18 Correct 1 ms 332 KB OK (n = 100, answer = NO)
19 Correct 2 ms 332 KB OK (n = 100, answer = YES)
20 Correct 2 ms 204 KB OK (n = 12, answer = YES)
21 Correct 2 ms 204 KB OK (n = 12, answer = YES)
22 Correct 1 ms 204 KB OK (n = 12, answer = NO)
23 Correct 1 ms 204 KB OK (n = 12, answer = NO)
24 Correct 2 ms 204 KB OK (n = 12, answer = YES)
25 Correct 2 ms 332 KB OK (n = 12, answer = YES)
26 Correct 1 ms 288 KB OK (n = 12, answer = YES)
27 Correct 2 ms 204 KB OK (n = 12, answer = YES)
28 Correct 2 ms 204 KB OK (n = 6, answer = YES)
29 Correct 2 ms 292 KB OK (n = 12, answer = YES)
30 Correct 4 ms 716 KB OK (n = 100, answer = NO)
31 Correct 2 ms 332 KB OK (n = 100, answer = YES)
32 Correct 5 ms 844 KB OK (n = 100, answer = NO)
33 Correct 3 ms 460 KB OK (n = 100, answer = YES)
34 Correct 2 ms 332 KB OK (n = 100, answer = YES)
35 Correct 10 ms 1332 KB OK (n = 100, answer = YES)
36 Correct 4 ms 588 KB OK (n = 100, answer = YES)
37 Correct 1 ms 204 KB OK (n = 28, answer = YES)
38 Correct 4 ms 588 KB OK (n = 27, answer = YES)
39 Correct 18 ms 2252 KB OK (n = 90, answer = YES)
40 Correct 2 ms 204 KB OK (n = 100, answer = YES)
41 Correct 2 ms 332 KB OK (n = 100, answer = YES)
42 Correct 2 ms 204 KB OK (n = 10, answer = YES)
43 Correct 2 ms 332 KB OK (n = 100, answer = YES)
44 Correct 4 ms 460 KB OK (n = 100, answer = YES)
45 Correct 7 ms 988 KB OK (n = 100, answer = YES)
46 Correct 2 ms 332 KB OK (n = 100, answer = YES)
47 Correct 26 ms 3076 KB OK (n = 100, answer = NO)
48 Correct 1 ms 332 KB OK (n = 100, answer = NO)
49 Correct 3 ms 588 KB OK (n = 100, answer = NO)
50 Correct 2 ms 332 KB OK (n = 100, answer = YES)
51 Correct 2 ms 332 KB OK (n = 100, answer = YES)
52 Correct 4 ms 672 KB OK (n = 100, answer = YES)
53 Correct 2 ms 204 KB OK (n = 100, answer = YES)
54 Correct 2 ms 332 KB OK (n = 100, answer = YES)
55 Correct 16 ms 26924 KB OK (n = 10000, answer = YES)
56 Runtime error 40 ms 65540 KB Execution killed with signal 9
57 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB OK (n = 1, answer = NO)
2 Correct 1 ms 204 KB OK (n = 1, answer = NO)
3 Correct 2 ms 288 KB OK (n = 1, answer = YES)
4 Correct 2 ms 296 KB OK (n = 2, answer = YES)
5 Correct 1 ms 292 KB OK (n = 2, answer = YES)
6 Correct 2 ms 204 KB OK (n = 3, answer = YES)
7 Correct 1 ms 204 KB OK (n = 3, answer = YES)
8 Correct 2 ms 204 KB OK (n = 3, answer = YES)
9 Correct 2 ms 204 KB OK (n = 3, answer = YES)
10 Correct 1 ms 204 KB OK (n = 3, answer = YES)
11 Correct 2 ms 240 KB OK (n = 3, answer = YES)
12 Correct 1 ms 204 KB OK (n = 3, answer = YES)
13 Correct 1 ms 204 KB OK (n = 3, answer = NO)
14 Correct 1 ms 204 KB OK (n = 3, answer = YES)
15 Correct 2 ms 204 KB OK (n = 3, answer = YES)
16 Correct 1 ms 204 KB OK (n = 3, answer = NO)
17 Correct 1 ms 204 KB OK (n = 3, answer = NO)
18 Correct 1 ms 332 KB OK (n = 100, answer = NO)
19 Correct 2 ms 332 KB OK (n = 100, answer = YES)
20 Correct 2 ms 204 KB OK (n = 12, answer = YES)
21 Correct 2 ms 204 KB OK (n = 12, answer = YES)
22 Correct 1 ms 204 KB OK (n = 12, answer = NO)
23 Correct 1 ms 204 KB OK (n = 12, answer = NO)
24 Correct 2 ms 204 KB OK (n = 12, answer = YES)
25 Correct 2 ms 332 KB OK (n = 12, answer = YES)
26 Correct 1 ms 288 KB OK (n = 12, answer = YES)
27 Correct 2 ms 204 KB OK (n = 12, answer = YES)
28 Correct 2 ms 204 KB OK (n = 6, answer = YES)
29 Correct 2 ms 292 KB OK (n = 12, answer = YES)
30 Correct 4 ms 716 KB OK (n = 100, answer = NO)
31 Correct 2 ms 332 KB OK (n = 100, answer = YES)
32 Correct 5 ms 844 KB OK (n = 100, answer = NO)
33 Correct 3 ms 460 KB OK (n = 100, answer = YES)
34 Correct 2 ms 332 KB OK (n = 100, answer = YES)
35 Correct 10 ms 1332 KB OK (n = 100, answer = YES)
36 Correct 4 ms 588 KB OK (n = 100, answer = YES)
37 Correct 1 ms 204 KB OK (n = 28, answer = YES)
38 Correct 4 ms 588 KB OK (n = 27, answer = YES)
39 Correct 18 ms 2252 KB OK (n = 90, answer = YES)
40 Correct 2 ms 204 KB OK (n = 100, answer = YES)
41 Correct 2 ms 332 KB OK (n = 100, answer = YES)
42 Correct 2 ms 204 KB OK (n = 10, answer = YES)
43 Correct 2 ms 332 KB OK (n = 100, answer = YES)
44 Correct 4 ms 460 KB OK (n = 100, answer = YES)
45 Correct 7 ms 988 KB OK (n = 100, answer = YES)
46 Correct 2 ms 332 KB OK (n = 100, answer = YES)
47 Correct 26 ms 3076 KB OK (n = 100, answer = NO)
48 Correct 1 ms 332 KB OK (n = 100, answer = NO)
49 Correct 3 ms 588 KB OK (n = 100, answer = NO)
50 Correct 2 ms 332 KB OK (n = 100, answer = YES)
51 Correct 2 ms 332 KB OK (n = 100, answer = YES)
52 Correct 4 ms 672 KB OK (n = 100, answer = YES)
53 Correct 2 ms 204 KB OK (n = 100, answer = YES)
54 Correct 2 ms 332 KB OK (n = 100, answer = YES)
55 Correct 16 ms 26924 KB OK (n = 10000, answer = YES)
56 Runtime error 40 ms 65540 KB Execution killed with signal 9
57 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB OK (n = 1, answer = NO)
2 Correct 1 ms 204 KB OK (n = 1, answer = NO)
3 Correct 2 ms 288 KB OK (n = 1, answer = YES)
4 Correct 2 ms 296 KB OK (n = 2, answer = YES)
5 Correct 1 ms 292 KB OK (n = 2, answer = YES)
6 Correct 2 ms 204 KB OK (n = 3, answer = YES)
7 Correct 1 ms 204 KB OK (n = 3, answer = YES)
8 Correct 2 ms 204 KB OK (n = 3, answer = YES)
9 Correct 2 ms 204 KB OK (n = 3, answer = YES)
10 Correct 1 ms 204 KB OK (n = 3, answer = YES)
11 Correct 2 ms 240 KB OK (n = 3, answer = YES)
12 Correct 1 ms 204 KB OK (n = 3, answer = YES)
13 Correct 1 ms 204 KB OK (n = 3, answer = NO)
14 Correct 1 ms 204 KB OK (n = 3, answer = YES)
15 Correct 2 ms 204 KB OK (n = 3, answer = YES)
16 Correct 1 ms 204 KB OK (n = 3, answer = NO)
17 Correct 1 ms 204 KB OK (n = 3, answer = NO)
18 Correct 1 ms 332 KB OK (n = 100, answer = NO)
19 Correct 2 ms 332 KB OK (n = 100, answer = YES)
20 Correct 2 ms 204 KB OK (n = 12, answer = YES)
21 Correct 2 ms 204 KB OK (n = 12, answer = YES)
22 Correct 1 ms 204 KB OK (n = 12, answer = NO)
23 Correct 1 ms 204 KB OK (n = 12, answer = NO)
24 Correct 2 ms 204 KB OK (n = 12, answer = YES)
25 Correct 2 ms 332 KB OK (n = 12, answer = YES)
26 Correct 1 ms 288 KB OK (n = 12, answer = YES)
27 Correct 2 ms 204 KB OK (n = 12, answer = YES)
28 Correct 2 ms 204 KB OK (n = 6, answer = YES)
29 Correct 2 ms 292 KB OK (n = 12, answer = YES)
30 Correct 4 ms 716 KB OK (n = 100, answer = NO)
31 Correct 2 ms 332 KB OK (n = 100, answer = YES)
32 Correct 5 ms 844 KB OK (n = 100, answer = NO)
33 Correct 3 ms 460 KB OK (n = 100, answer = YES)
34 Correct 2 ms 332 KB OK (n = 100, answer = YES)
35 Correct 10 ms 1332 KB OK (n = 100, answer = YES)
36 Correct 4 ms 588 KB OK (n = 100, answer = YES)
37 Correct 1 ms 204 KB OK (n = 28, answer = YES)
38 Correct 4 ms 588 KB OK (n = 27, answer = YES)
39 Correct 18 ms 2252 KB OK (n = 90, answer = YES)
40 Correct 2 ms 204 KB OK (n = 100, answer = YES)
41 Correct 2 ms 332 KB OK (n = 100, answer = YES)
42 Correct 2 ms 204 KB OK (n = 10, answer = YES)
43 Correct 2 ms 332 KB OK (n = 100, answer = YES)
44 Correct 4 ms 460 KB OK (n = 100, answer = YES)
45 Correct 7 ms 988 KB OK (n = 100, answer = YES)
46 Correct 2 ms 332 KB OK (n = 100, answer = YES)
47 Correct 26 ms 3076 KB OK (n = 100, answer = NO)
48 Correct 1 ms 332 KB OK (n = 100, answer = NO)
49 Correct 3 ms 588 KB OK (n = 100, answer = NO)
50 Correct 2 ms 332 KB OK (n = 100, answer = YES)
51 Correct 2 ms 332 KB OK (n = 100, answer = YES)
52 Correct 4 ms 672 KB OK (n = 100, answer = YES)
53 Correct 2 ms 204 KB OK (n = 100, answer = YES)
54 Correct 2 ms 332 KB OK (n = 100, answer = YES)
55 Correct 16 ms 26924 KB OK (n = 10000, answer = YES)
56 Runtime error 40 ms 65540 KB Execution killed with signal 9
57 Halted 0 ms 0 KB -