oj.uz

Submission #204296

# Submission time Handle Problem Language Result Execution time Memory
204296 2020-02-25T10:17:29 Z awlintqaa Detecting Molecules (IOI16_molecules) C++14
31 / 100
 1000 ms 18068 KB 
    #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
    #include <bits/stdc++.h>
    using namespace std;
    #define sqr 200
    #define mid (l+r)/2
    #define pb push_back
    #define ppb pop_back
    #define fi first
    #define se second
    #define lb lower_bound
    #define ub upper_bound
    #define ins insert
    #define era erase
    #define C continue
    #define mem(dp,i) memset(dp,i,sizeof(dp))
    #define mset multiset
    typedef long long ll;
    typedef short int si;
    typedef long double ld;
    typedef pair<int,int> pi;
    typedef pair<ll,ll> pll;
    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pi> vpi;
    typedef vector<pll> vpll;
    const ll mod=1e9+7;
    const ll inf= 4e18;
    const ld pai=acos(-1);
    #include "molecules.h"
    int n;
    int a[10009];
    int dp[2][500009];
    int p[500009];
    vi id[500009];
    vi path(int x){
            vi ret;
            while ( p[x]!=x && x>0){
                    ret.pb( id[ x-p[x] ].back() );
                    id [ x-p[x] ] .pop_back();
                    x = p[x];
            }
            return ret;
    }
    vi find_subset(int l, int u,vi w) {
            n = w.size();
            for ( int i =0 ;i < n;i ++ ){
                    id [ w[i] ] .pb (i);
            }
            dp[0][0]=1;
            for(int i =0 ;i < n ;i ++ ){
                    for(int j = 0 ;j <= 5e5 ;j++){
                            if ( j-w[i] >=0 && dp[0][ j -w[i] ] ){
                                    dp[1][j] = 1 ;
                                    if ( p[j] == 0 ) p [j] = j-w[i];
                            }
                            else dp [1][j]=dp[0][j];
                    }
                    for ( int j =0 ;j <= 5e5 ;j ++ ) {
                            dp [0][j] = dp[1][j];
                            dp [1][j] = 0;
                    }
              		int z = 0 ;
              		for( int j =l ;j <=u ;j ++ ) {
                      if ( dp[0][j]){
                        z=1;
                 		break;
                      }
                    }
              		if(z)break;
            }
            for ( int i =l ; i<=u ;i++ ){
                    if ( dp [0][i] ){
                            return path(i);
                    }
            }
            return std::vector<int>(0);
    }

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15992 KB OK (n = 1, answer = NO)
2 Correct 17 ms 15992 KB OK (n = 1, answer = NO)
3 Correct 16 ms 15992 KB OK (n = 1, answer = YES)
4 Correct 18 ms 15996 KB OK (n = 2, answer = YES)
5 Correct 16 ms 15992 KB OK (n = 2, answer = YES)
6 Correct 19 ms 15992 KB OK (n = 3, answer = YES)
7 Correct 19 ms 15996 KB OK (n = 3, answer = YES)
8 Correct 19 ms 15992 KB OK (n = 3, answer = YES)
9 Correct 17 ms 15992 KB OK (n = 3, answer = YES)
10 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
11 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
12 Correct 20 ms 15992 KB OK (n = 3, answer = YES)
13 Correct 19 ms 15992 KB OK (n = 3, answer = NO)
14 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
15 Correct 18 ms 15992 KB OK (n = 3, answer = YES)
16 Correct 19 ms 15992 KB OK (n = 3, answer = NO)
17 Correct 20 ms 15992 KB OK (n = 3, answer = NO)
18 Correct 147 ms 15992 KB OK (n = 100, answer = NO)
19 Correct 102 ms 15992 KB OK (n = 100, answer = YES)

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15992 KB OK (n = 12, answer = YES)
2 Correct 25 ms 15992 KB OK (n = 12, answer = YES)
3 Correct 29 ms 15992 KB OK (n = 12, answer = NO)
4 Correct 33 ms 15992 KB OK (n = 12, answer = NO)
5 Correct 23 ms 15992 KB OK (n = 12, answer = YES)
6 Correct 31 ms 15992 KB OK (n = 12, answer = YES)
7 Correct 26 ms 15992 KB OK (n = 12, answer = YES)
8 Correct 25 ms 15996 KB OK (n = 12, answer = YES)
9 Correct 22 ms 15992 KB OK (n = 6, answer = YES)
10 Correct 34 ms 15988 KB OK (n = 12, answer = YES)
11 Correct 142 ms 15992 KB OK (n = 100, answer = NO)
12 Correct 55 ms 15992 KB OK (n = 100, answer = YES)
13 Correct 138 ms 15992 KB OK (n = 100, answer = NO)
14 Correct 30 ms 15992 KB OK (n = 100, answer = YES)
15 Correct 46 ms 15992 KB OK (n = 100, answer = YES)
16 Correct 116 ms 16120 KB OK (n = 100, answer = YES)
17 Correct 106 ms 15992 KB OK (n = 100, answer = YES)

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15992 KB OK (n = 1, answer = NO)
2 Correct 17 ms 15992 KB OK (n = 1, answer = NO)
3 Correct 16 ms 15992 KB OK (n = 1, answer = YES)
4 Correct 18 ms 15996 KB OK (n = 2, answer = YES)
5 Correct 16 ms 15992 KB OK (n = 2, answer = YES)
6 Correct 19 ms 15992 KB OK (n = 3, answer = YES)
7 Correct 19 ms 15996 KB OK (n = 3, answer = YES)
8 Correct 19 ms 15992 KB OK (n = 3, answer = YES)
9 Correct 17 ms 15992 KB OK (n = 3, answer = YES)
10 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
11 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
12 Correct 20 ms 15992 KB OK (n = 3, answer = YES)
13 Correct 19 ms 15992 KB OK (n = 3, answer = NO)
14 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
15 Correct 18 ms 15992 KB OK (n = 3, answer = YES)
16 Correct 19 ms 15992 KB OK (n = 3, answer = NO)
17 Correct 20 ms 15992 KB OK (n = 3, answer = NO)
18 Correct 147 ms 15992 KB OK (n = 100, answer = NO)
19 Correct 102 ms 15992 KB OK (n = 100, answer = YES)
20 Correct 26 ms 15992 KB OK (n = 12, answer = YES)
21 Correct 25 ms 15992 KB OK (n = 12, answer = YES)
22 Correct 29 ms 15992 KB OK (n = 12, answer = NO)
23 Correct 33 ms 15992 KB OK (n = 12, answer = NO)
24 Correct 23 ms 15992 KB OK (n = 12, answer = YES)
25 Correct 31 ms 15992 KB OK (n = 12, answer = YES)
26 Correct 26 ms 15992 KB OK (n = 12, answer = YES)
27 Correct 25 ms 15996 KB OK (n = 12, answer = YES)
28 Correct 22 ms 15992 KB OK (n = 6, answer = YES)
29 Correct 34 ms 15988 KB OK (n = 12, answer = YES)
30 Correct 142 ms 15992 KB OK (n = 100, answer = NO)
31 Correct 55 ms 15992 KB OK (n = 100, answer = YES)
32 Correct 138 ms 15992 KB OK (n = 100, answer = NO)
33 Correct 30 ms 15992 KB OK (n = 100, answer = YES)
34 Correct 46 ms 15992 KB OK (n = 100, answer = YES)
35 Correct 116 ms 16120 KB OK (n = 100, answer = YES)
36 Correct 106 ms 15992 KB OK (n = 100, answer = YES)
37 Correct 27 ms 15992 KB OK (n = 28, answer = YES)
38 Correct 51 ms 15992 KB OK (n = 27, answer = YES)
39 Correct 136 ms 16120 KB OK (n = 90, answer = YES)
40 Correct 24 ms 15992 KB OK (n = 100, answer = YES)
41 Correct 144 ms 15996 KB OK (n = 100, answer = YES)
42 Correct 24 ms 15992 KB OK (n = 10, answer = YES)
43 Correct 95 ms 15992 KB OK (n = 100, answer = YES)
44 Correct 39 ms 15992 KB OK (n = 100, answer = YES)
45 Correct 59 ms 15992 KB OK (n = 100, answer = YES)
46 Correct 31 ms 15992 KB OK (n = 100, answer = YES)
47 Correct 142 ms 15992 KB OK (n = 100, answer = NO)
48 Correct 136 ms 16376 KB OK (n = 100, answer = NO)
49 Correct 136 ms 16248 KB OK (n = 100, answer = NO)
50 Correct 114 ms 16088 KB OK (n = 100, answer = YES)
51 Correct 84 ms 16028 KB OK (n = 100, answer = YES)
52 Correct 39 ms 16012 KB OK (n = 100, answer = YES)
53 Correct 23 ms 15992 KB OK (n = 100, answer = YES)
54 Correct 134 ms 15992 KB OK (n = 100, answer = YES)

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15992 KB OK (n = 1, answer = NO)
2 Correct 17 ms 15992 KB OK (n = 1, answer = NO)
3 Correct 16 ms 15992 KB OK (n = 1, answer = YES)
4 Correct 18 ms 15996 KB OK (n = 2, answer = YES)
5 Correct 16 ms 15992 KB OK (n = 2, answer = YES)
6 Correct 19 ms 15992 KB OK (n = 3, answer = YES)
7 Correct 19 ms 15996 KB OK (n = 3, answer = YES)
8 Correct 19 ms 15992 KB OK (n = 3, answer = YES)
9 Correct 17 ms 15992 KB OK (n = 3, answer = YES)
10 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
11 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
12 Correct 20 ms 15992 KB OK (n = 3, answer = YES)
13 Correct 19 ms 15992 KB OK (n = 3, answer = NO)
14 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
15 Correct 18 ms 15992 KB OK (n = 3, answer = YES)
16 Correct 19 ms 15992 KB OK (n = 3, answer = NO)
17 Correct 20 ms 15992 KB OK (n = 3, answer = NO)
18 Correct 147 ms 15992 KB OK (n = 100, answer = NO)
19 Correct 102 ms 15992 KB OK (n = 100, answer = YES)
20 Correct 26 ms 15992 KB OK (n = 12, answer = YES)
21 Correct 25 ms 15992 KB OK (n = 12, answer = YES)
22 Correct 29 ms 15992 KB OK (n = 12, answer = NO)
23 Correct 33 ms 15992 KB OK (n = 12, answer = NO)
24 Correct 23 ms 15992 KB OK (n = 12, answer = YES)
25 Correct 31 ms 15992 KB OK (n = 12, answer = YES)
26 Correct 26 ms 15992 KB OK (n = 12, answer = YES)
27 Correct 25 ms 15996 KB OK (n = 12, answer = YES)
28 Correct 22 ms 15992 KB OK (n = 6, answer = YES)
29 Correct 34 ms 15988 KB OK (n = 12, answer = YES)
30 Correct 142 ms 15992 KB OK (n = 100, answer = NO)
31 Correct 55 ms 15992 KB OK (n = 100, answer = YES)
32 Correct 138 ms 15992 KB OK (n = 100, answer = NO)
33 Correct 30 ms 15992 KB OK (n = 100, answer = YES)
34 Correct 46 ms 15992 KB OK (n = 100, answer = YES)
35 Correct 116 ms 16120 KB OK (n = 100, answer = YES)
36 Correct 106 ms 15992 KB OK (n = 100, answer = YES)
37 Correct 27 ms 15992 KB OK (n = 28, answer = YES)
38 Correct 51 ms 15992 KB OK (n = 27, answer = YES)
39 Correct 136 ms 16120 KB OK (n = 90, answer = YES)
40 Correct 24 ms 15992 KB OK (n = 100, answer = YES)
41 Correct 144 ms 15996 KB OK (n = 100, answer = YES)
42 Correct 24 ms 15992 KB OK (n = 10, answer = YES)
43 Correct 95 ms 15992 KB OK (n = 100, answer = YES)
44 Correct 39 ms 15992 KB OK (n = 100, answer = YES)
45 Correct 59 ms 15992 KB OK (n = 100, answer = YES)
46 Correct 31 ms 15992 KB OK (n = 100, answer = YES)
47 Correct 142 ms 15992 KB OK (n = 100, answer = NO)
48 Correct 136 ms 16376 KB OK (n = 100, answer = NO)
49 Correct 136 ms 16248 KB OK (n = 100, answer = NO)
50 Correct 114 ms 16088 KB OK (n = 100, answer = YES)
51 Correct 84 ms 16028 KB OK (n = 100, answer = YES)
52 Correct 39 ms 16012 KB OK (n = 100, answer = YES)
53 Correct 23 ms 15992 KB OK (n = 100, answer = YES)
54 Correct 134 ms 15992 KB OK (n = 100, answer = YES)
55 Correct 854 ms 16504 KB OK (n = 10000, answer = YES)
56 Correct 142 ms 16248 KB OK (n = 10000, answer = YES)
57 Correct 223 ms 16760 KB OK (n = 10000, answer = YES)
58 Correct 28 ms 16120 KB OK (n = 10000, answer = YES)
59 Correct 278 ms 16376 KB OK (n = 10000, answer = YES)
60 Correct 35 ms 16124 KB OK (n = 10000, answer = YES)
61 Execution timed out 1090 ms 18068 KB Time limit exceeded
62 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15992 KB OK (n = 1, answer = NO)
2 Correct 17 ms 15992 KB OK (n = 1, answer = NO)
3 Correct 16 ms 15992 KB OK (n = 1, answer = YES)
4 Correct 18 ms 15996 KB OK (n = 2, answer = YES)
5 Correct 16 ms 15992 KB OK (n = 2, answer = YES)
6 Correct 19 ms 15992 KB OK (n = 3, answer = YES)
7 Correct 19 ms 15996 KB OK (n = 3, answer = YES)
8 Correct 19 ms 15992 KB OK (n = 3, answer = YES)
9 Correct 17 ms 15992 KB OK (n = 3, answer = YES)
10 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
11 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
12 Correct 20 ms 15992 KB OK (n = 3, answer = YES)
13 Correct 19 ms 15992 KB OK (n = 3, answer = NO)
14 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
15 Correct 18 ms 15992 KB OK (n = 3, answer = YES)
16 Correct 19 ms 15992 KB OK (n = 3, answer = NO)
17 Correct 20 ms 15992 KB OK (n = 3, answer = NO)
18 Correct 147 ms 15992 KB OK (n = 100, answer = NO)
19 Correct 102 ms 15992 KB OK (n = 100, answer = YES)
20 Correct 26 ms 15992 KB OK (n = 12, answer = YES)
21 Correct 25 ms 15992 KB OK (n = 12, answer = YES)
22 Correct 29 ms 15992 KB OK (n = 12, answer = NO)
23 Correct 33 ms 15992 KB OK (n = 12, answer = NO)
24 Correct 23 ms 15992 KB OK (n = 12, answer = YES)
25 Correct 31 ms 15992 KB OK (n = 12, answer = YES)
26 Correct 26 ms 15992 KB OK (n = 12, answer = YES)
27 Correct 25 ms 15996 KB OK (n = 12, answer = YES)
28 Correct 22 ms 15992 KB OK (n = 6, answer = YES)
29 Correct 34 ms 15988 KB OK (n = 12, answer = YES)
30 Correct 142 ms 15992 KB OK (n = 100, answer = NO)
31 Correct 55 ms 15992 KB OK (n = 100, answer = YES)
32 Correct 138 ms 15992 KB OK (n = 100, answer = NO)
33 Correct 30 ms 15992 KB OK (n = 100, answer = YES)
34 Correct 46 ms 15992 KB OK (n = 100, answer = YES)
35 Correct 116 ms 16120 KB OK (n = 100, answer = YES)
36 Correct 106 ms 15992 KB OK (n = 100, answer = YES)
37 Correct 27 ms 15992 KB OK (n = 28, answer = YES)
38 Correct 51 ms 15992 KB OK (n = 27, answer = YES)
39 Correct 136 ms 16120 KB OK (n = 90, answer = YES)
40 Correct 24 ms 15992 KB OK (n = 100, answer = YES)
41 Correct 144 ms 15996 KB OK (n = 100, answer = YES)
42 Correct 24 ms 15992 KB OK (n = 10, answer = YES)
43 Correct 95 ms 15992 KB OK (n = 100, answer = YES)
44 Correct 39 ms 15992 KB OK (n = 100, answer = YES)
45 Correct 59 ms 15992 KB OK (n = 100, answer = YES)
46 Correct 31 ms 15992 KB OK (n = 100, answer = YES)
47 Correct 142 ms 15992 KB OK (n = 100, answer = NO)
48 Correct 136 ms 16376 KB OK (n = 100, answer = NO)
49 Correct 136 ms 16248 KB OK (n = 100, answer = NO)
50 Correct 114 ms 16088 KB OK (n = 100, answer = YES)
51 Correct 84 ms 16028 KB OK (n = 100, answer = YES)
52 Correct 39 ms 16012 KB OK (n = 100, answer = YES)
53 Correct 23 ms 15992 KB OK (n = 100, answer = YES)
54 Correct 134 ms 15992 KB OK (n = 100, answer = YES)
55 Correct 854 ms 16504 KB OK (n = 10000, answer = YES)
56 Correct 142 ms 16248 KB OK (n = 10000, answer = YES)
57 Correct 223 ms 16760 KB OK (n = 10000, answer = YES)
58 Correct 28 ms 16120 KB OK (n = 10000, answer = YES)
59 Correct 278 ms 16376 KB OK (n = 10000, answer = YES)
60 Correct 35 ms 16124 KB OK (n = 10000, answer = YES)
61 Execution timed out 1090 ms 18068 KB Time limit exceeded
62 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15992 KB OK (n = 1, answer = NO)
2 Correct 17 ms 15992 KB OK (n = 1, answer = NO)
3 Correct 16 ms 15992 KB OK (n = 1, answer = YES)
4 Correct 18 ms 15996 KB OK (n = 2, answer = YES)
5 Correct 16 ms 15992 KB OK (n = 2, answer = YES)
6 Correct 19 ms 15992 KB OK (n = 3, answer = YES)
7 Correct 19 ms 15996 KB OK (n = 3, answer = YES)
8 Correct 19 ms 15992 KB OK (n = 3, answer = YES)
9 Correct 17 ms 15992 KB OK (n = 3, answer = YES)
10 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
11 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
12 Correct 20 ms 15992 KB OK (n = 3, answer = YES)
13 Correct 19 ms 15992 KB OK (n = 3, answer = NO)
14 Correct 16 ms 15992 KB OK (n = 3, answer = YES)
15 Correct 18 ms 15992 KB OK (n = 3, answer = YES)
16 Correct 19 ms 15992 KB OK (n = 3, answer = NO)
17 Correct 20 ms 15992 KB OK (n = 3, answer = NO)
18 Correct 147 ms 15992 KB OK (n = 100, answer = NO)
19 Correct 102 ms 15992 KB OK (n = 100, answer = YES)
20 Correct 26 ms 15992 KB OK (n = 12, answer = YES)
21 Correct 25 ms 15992 KB OK (n = 12, answer = YES)
22 Correct 29 ms 15992 KB OK (n = 12, answer = NO)
23 Correct 33 ms 15992 KB OK (n = 12, answer = NO)
24 Correct 23 ms 15992 KB OK (n = 12, answer = YES)
25 Correct 31 ms 15992 KB OK (n = 12, answer = YES)
26 Correct 26 ms 15992 KB OK (n = 12, answer = YES)
27 Correct 25 ms 15996 KB OK (n = 12, answer = YES)
28 Correct 22 ms 15992 KB OK (n = 6, answer = YES)
29 Correct 34 ms 15988 KB OK (n = 12, answer = YES)
30 Correct 142 ms 15992 KB OK (n = 100, answer = NO)
31 Correct 55 ms 15992 KB OK (n = 100, answer = YES)
32 Correct 138 ms 15992 KB OK (n = 100, answer = NO)
33 Correct 30 ms 15992 KB OK (n = 100, answer = YES)
34 Correct 46 ms 15992 KB OK (n = 100, answer = YES)
35 Correct 116 ms 16120 KB OK (n = 100, answer = YES)
36 Correct 106 ms 15992 KB OK (n = 100, answer = YES)
37 Correct 27 ms 15992 KB OK (n = 28, answer = YES)
38 Correct 51 ms 15992 KB OK (n = 27, answer = YES)
39 Correct 136 ms 16120 KB OK (n = 90, answer = YES)
40 Correct 24 ms 15992 KB OK (n = 100, answer = YES)
41 Correct 144 ms 15996 KB OK (n = 100, answer = YES)
42 Correct 24 ms 15992 KB OK (n = 10, answer = YES)
43 Correct 95 ms 15992 KB OK (n = 100, answer = YES)
44 Correct 39 ms 15992 KB OK (n = 100, answer = YES)
45 Correct 59 ms 15992 KB OK (n = 100, answer = YES)
46 Correct 31 ms 15992 KB OK (n = 100, answer = YES)
47 Correct 142 ms 15992 KB OK (n = 100, answer = NO)
48 Correct 136 ms 16376 KB OK (n = 100, answer = NO)
49 Correct 136 ms 16248 KB OK (n = 100, answer = NO)
50 Correct 114 ms 16088 KB OK (n = 100, answer = YES)
51 Correct 84 ms 16028 KB OK (n = 100, answer = YES)
52 Correct 39 ms 16012 KB OK (n = 100, answer = YES)
53 Correct 23 ms 15992 KB OK (n = 100, answer = YES)
54 Correct 134 ms 15992 KB OK (n = 100, answer = YES)
55 Correct 854 ms 16504 KB OK (n = 10000, answer = YES)
56 Correct 142 ms 16248 KB OK (n = 10000, answer = YES)
57 Correct 223 ms 16760 KB OK (n = 10000, answer = YES)
58 Correct 28 ms 16120 KB OK (n = 10000, answer = YES)
59 Correct 278 ms 16376 KB OK (n = 10000, answer = YES)
60 Correct 35 ms 16124 KB OK (n = 10000, answer = YES)
61 Execution timed out 1090 ms 18068 KB Time limit exceeded
62 Halted 0 ms 0 KB -