제출 #204296

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
204296		awlintqaa	Detecting Molecules (IOI16_molecules)	C++14	31 / 100	1090 ms	18068 KiB

molecules

    #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 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31