oj.uz

Submission #565056

# Submission time Handle Problem Language Result Execution time Memory
565056 2022-05-20T08:21:39 Z MadokaMagicaFan Detecting Molecules (IOI16_molecules) C++14
31 / 100
 1000 ms 10508 KB 
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;

#define all(v)                      v.begin(), v.end()
#define rall(v)                     v.rbegin(), v.rend()
#define sz(v)                       ((int)v.size())

#define forn(i,n)                   for(int i = 0; i < n; ++i)
#define forbe(i,b,e)                for(int i = b; i < e; ++i)

#define pb                          push_back

#define pry                         puts("YES")
#define prn                         puts("NO")
#define endl                        '\n'

#define fst                         first
#define scn                         second

int
find_subset(int *l)
{
    return 0;
}

vector<int>
find_subset(int l, int r, vector<int> w)
{
    int n = sz(w);
    map<int,int> p;
    set<ll> vals;
    vals.insert(0);
    p[0] = -1;

    vector<ll> ws;
    ll ans = -1;
    for (int i = 0; i < n; ++i) {
        ws.clear();

        for (auto u : vals)
            ws.pb(u+w[i]);

        for (auto u : ws) {
            if (vals.find(u) == vals.end())
                p[u] = i;
            vals.insert(u);

            if (l <= u && r >= u){
                ans = u;
                i = n;
                break;
            }
        }
    }

    vector<int> result;
    if (ans == -1)
        return result;

    while (p[ans] != -1) {
        result.pb(p[ans]);
        ans = ans - w[p[ans]];
    }

    return result;
}

#ifdef ONPC
void
solve()
{

    const int N = 1e4;
    int n, l, r;

    cin >> n >> l >> r;
    int w[N];
    for (int i = 0; i < n; ++i)
        cin >> w[i];
    int result[N];

    int ans = find_subset(l,r,w,n, result);

    cout << ans << endl;
    return;
    for (int i = 0; i < ans; ++i) {
        cout << w[result[i]-1] << ' ';
    }
    cout << endl;
}

int32_t
main()
{
    freopen("in", "r", stdin);
    int t = 1;
    cin >> t;
    while(t--)
        solve();
}
#endif

Subtask #1
9.0 / 9.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB OK (n = 12, answer = YES)
2 Correct 0 ms 212 KB OK (n = 12, answer = YES)
3 Correct 0 ms 212 KB OK (n = 12, answer = NO)
4 Correct 1 ms 212 KB OK (n = 12, answer = NO)
5 Correct 0 ms 212 KB OK (n = 12, answer = YES)
6 Correct 1 ms 212 KB OK (n = 12, answer = YES)
7 Correct 1 ms 212 KB OK (n = 12, answer = YES)
8 Correct 1 ms 212 KB OK (n = 12, answer = YES)
9 Correct 1 ms 212 KB OK (n = 6, answer = YES)
10 Correct 1 ms 212 KB OK (n = 12, answer = YES)
11 Correct 1 ms 212 KB OK (n = 100, answer = NO)
12 Correct 1 ms 212 KB OK (n = 100, answer = YES)
13 Correct 1 ms 296 KB OK (n = 100, answer = NO)
14 Correct 1 ms 212 KB OK (n = 100, answer = YES)
15 Correct 1 ms 212 KB OK (n = 100, answer = YES)
16 Correct 2 ms 468 KB OK (n = 100, answer = YES)
17 Correct 1 ms 340 KB OK (n = 100, answer = YES)

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB OK (n = 1, answer = NO)
2 Correct 0 ms 212 KB OK (n = 1, answer = NO)
3 Correct 0 ms 212 KB OK (n = 1, answer = YES)
4 Correct 1 ms 212 KB OK (n = 2, answer = YES)
5 Correct 1 ms 212 KB OK (n = 2, answer = YES)
6 Correct 1 ms 212 KB OK (n = 3, answer = YES)
7 Correct 0 ms 212 KB OK (n = 3, answer = YES)
8 Correct 1 ms 212 KB OK (n = 3, answer = YES)
9 Correct 0 ms 296 KB OK (n = 3, answer = YES)
10 Correct 1 ms 212 KB OK (n = 3, answer = YES)
11 Correct 1 ms 212 KB OK (n = 3, answer = YES)
12 Correct 0 ms 212 KB OK (n = 3, answer = YES)
13 Correct 0 ms 212 KB OK (n = 3, answer = NO)
14 Correct 1 ms 212 KB OK (n = 3, answer = YES)
15 Correct 0 ms 212 KB OK (n = 3, answer = YES)
16 Correct 1 ms 304 KB OK (n = 3, answer = NO)
17 Correct 1 ms 212 KB OK (n = 3, answer = NO)
18 Correct 1 ms 212 KB OK (n = 100, answer = NO)
19 Correct 1 ms 300 KB OK (n = 100, answer = YES)
20 Correct 1 ms 212 KB OK (n = 12, answer = YES)
21 Correct 0 ms 212 KB OK (n = 12, answer = YES)
22 Correct 0 ms 212 KB OK (n = 12, answer = NO)
23 Correct 1 ms 212 KB OK (n = 12, answer = NO)
24 Correct 0 ms 212 KB OK (n = 12, answer = YES)
25 Correct 1 ms 212 KB OK (n = 12, answer = YES)
26 Correct 1 ms 212 KB OK (n = 12, answer = YES)
27 Correct 1 ms 212 KB OK (n = 12, answer = YES)
28 Correct 1 ms 212 KB OK (n = 6, answer = YES)
29 Correct 1 ms 212 KB OK (n = 12, answer = YES)
30 Correct 1 ms 212 KB OK (n = 100, answer = NO)
31 Correct 1 ms 212 KB OK (n = 100, answer = YES)
32 Correct 1 ms 296 KB OK (n = 100, answer = NO)
33 Correct 1 ms 212 KB OK (n = 100, answer = YES)
34 Correct 1 ms 212 KB OK (n = 100, answer = YES)
35 Correct 2 ms 468 KB OK (n = 100, answer = YES)
36 Correct 1 ms 340 KB OK (n = 100, answer = YES)
37 Correct 1 ms 212 KB OK (n = 28, answer = YES)
38 Correct 2 ms 340 KB OK (n = 27, answer = YES)
39 Correct 37 ms 1064 KB OK (n = 90, answer = YES)
40 Correct 1 ms 212 KB OK (n = 100, answer = YES)
41 Correct 4 ms 428 KB OK (n = 100, answer = YES)
42 Correct 1 ms 212 KB OK (n = 10, answer = YES)
43 Correct 3 ms 340 KB OK (n = 100, answer = YES)
44 Correct 1 ms 340 KB OK (n = 100, answer = YES)
45 Correct 1 ms 340 KB OK (n = 100, answer = YES)
46 Correct 1 ms 212 KB OK (n = 100, answer = YES)
47 Correct 3 ms 340 KB OK (n = 100, answer = NO)
48 Correct 65 ms 1888 KB OK (n = 100, answer = NO)
49 Correct 397 ms 6304 KB OK (n = 100, answer = NO)
50 Correct 4 ms 340 KB OK (n = 100, answer = YES)
51 Correct 2 ms 296 KB OK (n = 100, answer = YES)
52 Correct 1 ms 340 KB OK (n = 100, answer = YES)
53 Correct 0 ms 212 KB OK (n = 100, answer = YES)
54 Correct 3 ms 468 KB OK (n = 100, answer = YES)

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB OK (n = 1, answer = NO)
2 Correct 0 ms 212 KB OK (n = 1, answer = NO)
3 Correct 0 ms 212 KB OK (n = 1, answer = YES)
4 Correct 1 ms 212 KB OK (n = 2, answer = YES)
5 Correct 1 ms 212 KB OK (n = 2, answer = YES)
6 Correct 1 ms 212 KB OK (n = 3, answer = YES)
7 Correct 0 ms 212 KB OK (n = 3, answer = YES)
8 Correct 1 ms 212 KB OK (n = 3, answer = YES)
9 Correct 0 ms 296 KB OK (n = 3, answer = YES)
10 Correct 1 ms 212 KB OK (n = 3, answer = YES)
11 Correct 1 ms 212 KB OK (n = 3, answer = YES)
12 Correct 0 ms 212 KB OK (n = 3, answer = YES)
13 Correct 0 ms 212 KB OK (n = 3, answer = NO)
14 Correct 1 ms 212 KB OK (n = 3, answer = YES)
15 Correct 0 ms 212 KB OK (n = 3, answer = YES)
16 Correct 1 ms 304 KB OK (n = 3, answer = NO)
17 Correct 1 ms 212 KB OK (n = 3, answer = NO)
18 Correct 1 ms 212 KB OK (n = 100, answer = NO)
19 Correct 1 ms 300 KB OK (n = 100, answer = YES)
20 Correct 1 ms 212 KB OK (n = 12, answer = YES)
21 Correct 0 ms 212 KB OK (n = 12, answer = YES)
22 Correct 0 ms 212 KB OK (n = 12, answer = NO)
23 Correct 1 ms 212 KB OK (n = 12, answer = NO)
24 Correct 0 ms 212 KB OK (n = 12, answer = YES)
25 Correct 1 ms 212 KB OK (n = 12, answer = YES)
26 Correct 1 ms 212 KB OK (n = 12, answer = YES)
27 Correct 1 ms 212 KB OK (n = 12, answer = YES)
28 Correct 1 ms 212 KB OK (n = 6, answer = YES)
29 Correct 1 ms 212 KB OK (n = 12, answer = YES)
30 Correct 1 ms 212 KB OK (n = 100, answer = NO)
31 Correct 1 ms 212 KB OK (n = 100, answer = YES)
32 Correct 1 ms 296 KB OK (n = 100, answer = NO)
33 Correct 1 ms 212 KB OK (n = 100, answer = YES)
34 Correct 1 ms 212 KB OK (n = 100, answer = YES)
35 Correct 2 ms 468 KB OK (n = 100, answer = YES)
36 Correct 1 ms 340 KB OK (n = 100, answer = YES)
37 Correct 1 ms 212 KB OK (n = 28, answer = YES)
38 Correct 2 ms 340 KB OK (n = 27, answer = YES)
39 Correct 37 ms 1064 KB OK (n = 90, answer = YES)
40 Correct 1 ms 212 KB OK (n = 100, answer = YES)
41 Correct 4 ms 428 KB OK (n = 100, answer = YES)
42 Correct 1 ms 212 KB OK (n = 10, answer = YES)
43 Correct 3 ms 340 KB OK (n = 100, answer = YES)
44 Correct 1 ms 340 KB OK (n = 100, answer = YES)
45 Correct 1 ms 340 KB OK (n = 100, answer = YES)
46 Correct 1 ms 212 KB OK (n = 100, answer = YES)
47 Correct 3 ms 340 KB OK (n = 100, answer = NO)
48 Correct 65 ms 1888 KB OK (n = 100, answer = NO)
49 Correct 397 ms 6304 KB OK (n = 100, answer = NO)
50 Correct 4 ms 340 KB OK (n = 100, answer = YES)
51 Correct 2 ms 296 KB OK (n = 100, answer = YES)
52 Correct 1 ms 340 KB OK (n = 100, answer = YES)
53 Correct 0 ms 212 KB OK (n = 100, answer = YES)
54 Correct 3 ms 468 KB OK (n = 100, answer = YES)
55 Correct 287 ms 1328 KB OK (n = 10000, answer = YES)
56 Correct 45 ms 1336 KB OK (n = 10000, answer = YES)
57 Correct 252 ms 4700 KB OK (n = 10000, answer = YES)
58 Correct 2 ms 340 KB OK (n = 10000, answer = YES)
59 Correct 86 ms 1392 KB OK (n = 10000, answer = YES)
60 Correct 2 ms 340 KB OK (n = 10000, answer = YES)
61 Execution timed out 1083 ms 10508 KB Time limit exceeded
62 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB OK (n = 1, answer = NO)
2 Correct 0 ms 212 KB OK (n = 1, answer = NO)
3 Correct 0 ms 212 KB OK (n = 1, answer = YES)
4 Correct 1 ms 212 KB OK (n = 2, answer = YES)
5 Correct 1 ms 212 KB OK (n = 2, answer = YES)
6 Correct 1 ms 212 KB OK (n = 3, answer = YES)
7 Correct 0 ms 212 KB OK (n = 3, answer = YES)
8 Correct 1 ms 212 KB OK (n = 3, answer = YES)
9 Correct 0 ms 296 KB OK (n = 3, answer = YES)
10 Correct 1 ms 212 KB OK (n = 3, answer = YES)
11 Correct 1 ms 212 KB OK (n = 3, answer = YES)
12 Correct 0 ms 212 KB OK (n = 3, answer = YES)
13 Correct 0 ms 212 KB OK (n = 3, answer = NO)
14 Correct 1 ms 212 KB OK (n = 3, answer = YES)
15 Correct 0 ms 212 KB OK (n = 3, answer = YES)
16 Correct 1 ms 304 KB OK (n = 3, answer = NO)
17 Correct 1 ms 212 KB OK (n = 3, answer = NO)
18 Correct 1 ms 212 KB OK (n = 100, answer = NO)
19 Correct 1 ms 300 KB OK (n = 100, answer = YES)
20 Correct 1 ms 212 KB OK (n = 12, answer = YES)
21 Correct 0 ms 212 KB OK (n = 12, answer = YES)
22 Correct 0 ms 212 KB OK (n = 12, answer = NO)
23 Correct 1 ms 212 KB OK (n = 12, answer = NO)
24 Correct 0 ms 212 KB OK (n = 12, answer = YES)
25 Correct 1 ms 212 KB OK (n = 12, answer = YES)
26 Correct 1 ms 212 KB OK (n = 12, answer = YES)
27 Correct 1 ms 212 KB OK (n = 12, answer = YES)
28 Correct 1 ms 212 KB OK (n = 6, answer = YES)
29 Correct 1 ms 212 KB OK (n = 12, answer = YES)
30 Correct 1 ms 212 KB OK (n = 100, answer = NO)
31 Correct 1 ms 212 KB OK (n = 100, answer = YES)
32 Correct 1 ms 296 KB OK (n = 100, answer = NO)
33 Correct 1 ms 212 KB OK (n = 100, answer = YES)
34 Correct 1 ms 212 KB OK (n = 100, answer = YES)
35 Correct 2 ms 468 KB OK (n = 100, answer = YES)
36 Correct 1 ms 340 KB OK (n = 100, answer = YES)
37 Correct 1 ms 212 KB OK (n = 28, answer = YES)
38 Correct 2 ms 340 KB OK (n = 27, answer = YES)
39 Correct 37 ms 1064 KB OK (n = 90, answer = YES)
40 Correct 1 ms 212 KB OK (n = 100, answer = YES)
41 Correct 4 ms 428 KB OK (n = 100, answer = YES)
42 Correct 1 ms 212 KB OK (n = 10, answer = YES)
43 Correct 3 ms 340 KB OK (n = 100, answer = YES)
44 Correct 1 ms 340 KB OK (n = 100, answer = YES)
45 Correct 1 ms 340 KB OK (n = 100, answer = YES)
46 Correct 1 ms 212 KB OK (n = 100, answer = YES)
47 Correct 3 ms 340 KB OK (n = 100, answer = NO)
48 Correct 65 ms 1888 KB OK (n = 100, answer = NO)
49 Correct 397 ms 6304 KB OK (n = 100, answer = NO)
50 Correct 4 ms 340 KB OK (n = 100, answer = YES)
51 Correct 2 ms 296 KB OK (n = 100, answer = YES)
52 Correct 1 ms 340 KB OK (n = 100, answer = YES)
53 Correct 0 ms 212 KB OK (n = 100, answer = YES)
54 Correct 3 ms 468 KB OK (n = 100, answer = YES)
55 Correct 287 ms 1328 KB OK (n = 10000, answer = YES)
56 Correct 45 ms 1336 KB OK (n = 10000, answer = YES)
57 Correct 252 ms 4700 KB OK (n = 10000, answer = YES)
58 Correct 2 ms 340 KB OK (n = 10000, answer = YES)
59 Correct 86 ms 1392 KB OK (n = 10000, answer = YES)
60 Correct 2 ms 340 KB OK (n = 10000, answer = YES)
61 Execution timed out 1083 ms 10508 KB Time limit exceeded
62 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB OK (n = 1, answer = NO)
2 Correct 0 ms 212 KB OK (n = 1, answer = NO)
3 Correct 0 ms 212 KB OK (n = 1, answer = YES)
4 Correct 1 ms 212 KB OK (n = 2, answer = YES)
5 Correct 1 ms 212 KB OK (n = 2, answer = YES)
6 Correct 1 ms 212 KB OK (n = 3, answer = YES)
7 Correct 0 ms 212 KB OK (n = 3, answer = YES)
8 Correct 1 ms 212 KB OK (n = 3, answer = YES)
9 Correct 0 ms 296 KB OK (n = 3, answer = YES)
10 Correct 1 ms 212 KB OK (n = 3, answer = YES)
11 Correct 1 ms 212 KB OK (n = 3, answer = YES)
12 Correct 0 ms 212 KB OK (n = 3, answer = YES)
13 Correct 0 ms 212 KB OK (n = 3, answer = NO)
14 Correct 1 ms 212 KB OK (n = 3, answer = YES)
15 Correct 0 ms 212 KB OK (n = 3, answer = YES)
16 Correct 1 ms 304 KB OK (n = 3, answer = NO)
17 Correct 1 ms 212 KB OK (n = 3, answer = NO)
18 Correct 1 ms 212 KB OK (n = 100, answer = NO)
19 Correct 1 ms 300 KB OK (n = 100, answer = YES)
20 Correct 1 ms 212 KB OK (n = 12, answer = YES)
21 Correct 0 ms 212 KB OK (n = 12, answer = YES)
22 Correct 0 ms 212 KB OK (n = 12, answer = NO)
23 Correct 1 ms 212 KB OK (n = 12, answer = NO)
24 Correct 0 ms 212 KB OK (n = 12, answer = YES)
25 Correct 1 ms 212 KB OK (n = 12, answer = YES)
26 Correct 1 ms 212 KB OK (n = 12, answer = YES)
27 Correct 1 ms 212 KB OK (n = 12, answer = YES)
28 Correct 1 ms 212 KB OK (n = 6, answer = YES)
29 Correct 1 ms 212 KB OK (n = 12, answer = YES)
30 Correct 1 ms 212 KB OK (n = 100, answer = NO)
31 Correct 1 ms 212 KB OK (n = 100, answer = YES)
32 Correct 1 ms 296 KB OK (n = 100, answer = NO)
33 Correct 1 ms 212 KB OK (n = 100, answer = YES)
34 Correct 1 ms 212 KB OK (n = 100, answer = YES)
35 Correct 2 ms 468 KB OK (n = 100, answer = YES)
36 Correct 1 ms 340 KB OK (n = 100, answer = YES)
37 Correct 1 ms 212 KB OK (n = 28, answer = YES)
38 Correct 2 ms 340 KB OK (n = 27, answer = YES)
39 Correct 37 ms 1064 KB OK (n = 90, answer = YES)
40 Correct 1 ms 212 KB OK (n = 100, answer = YES)
41 Correct 4 ms 428 KB OK (n = 100, answer = YES)
42 Correct 1 ms 212 KB OK (n = 10, answer = YES)
43 Correct 3 ms 340 KB OK (n = 100, answer = YES)
44 Correct 1 ms 340 KB OK (n = 100, answer = YES)
45 Correct 1 ms 340 KB OK (n = 100, answer = YES)
46 Correct 1 ms 212 KB OK (n = 100, answer = YES)
47 Correct 3 ms 340 KB OK (n = 100, answer = NO)
48 Correct 65 ms 1888 KB OK (n = 100, answer = NO)
49 Correct 397 ms 6304 KB OK (n = 100, answer = NO)
50 Correct 4 ms 340 KB OK (n = 100, answer = YES)
51 Correct 2 ms 296 KB OK (n = 100, answer = YES)
52 Correct 1 ms 340 KB OK (n = 100, answer = YES)
53 Correct 0 ms 212 KB OK (n = 100, answer = YES)
54 Correct 3 ms 468 KB OK (n = 100, answer = YES)
55 Correct 287 ms 1328 KB OK (n = 10000, answer = YES)
56 Correct 45 ms 1336 KB OK (n = 10000, answer = YES)
57 Correct 252 ms 4700 KB OK (n = 10000, answer = YES)
58 Correct 2 ms 340 KB OK (n = 10000, answer = YES)
59 Correct 86 ms 1392 KB OK (n = 10000, answer = YES)
60 Correct 2 ms 340 KB OK (n = 10000, answer = YES)
61 Execution timed out 1083 ms 10508 KB Time limit exceeded
62 Halted 0 ms 0 KB -