sinhachhavi3's blog

By sinhachhavi3, history, 5 weeks ago, In English

include<bits/stdc++.h>

using namespace std;

//#include<ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;

define ll long long

//#define ordered_set tree<ll,null_type,less,rb_tree_tag,tree_order_statistics_node_update>

define pb push_back

define mp make_pair

define mod (ll)1000000007

define N (int)200005

define maxN (int)1000002

define MOD (ll)998244353

//there are other prime numbers as well such as 1e9+9,1e6+69

define inf (ll)LLONG_MAX

define ninf (ll)LLONG_MIN

define F first

define S second

define pi pair<int,int>

define pll pair<long long int,long long int>

define pqi priority_queue //default max heap//multiply with -1 to convert to min heap

define pqii priority_queue <int,vector,greater>

define pq priority_queue <pi,vector , greater>

define rep(i,a,b) for(int i=a;i<(int)b;i+=1)

define fr(i,a,b) for(ll i=a;i<(ll)b;i+=1)

define fre(i,a,b) for(ll i=a;i<=(ll)b;i+=1)

define rfre(i,a,b) for(ll i=a;i>=(ll)b;i-=1)

define fio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

void solve() { int n;cin>>n;

vector<int> vec(n);

int sum=0;

for(int i=0;i<n;i+=1) {cin>>vec[i];sum+=vec[i];}

//int sum=0;



//there is another one that is partial sum 

if(sum%2) {cout<<0<<"\n";return;}

int x=sum/2;

bool dp[n+1][sum+1];

bool f=0;

for(int i=0;i<=n;i+=1)
{
    for(int j=0;j<=sum;j+=1) dp[i][j]=0;
}

for(int i=0;i<n;i+=1)
{
    dp[i+1][vec[i]]=1;
}

dp[0][0]=1;

//empty subset with 0 sum 
for(int i=1;i<=n;i+=1)
{
    for(int k=0;k<=sum;k+=1)
    {
        //dp[i][k] is true if the set of first i elements can yield a sum of k else no 
        if(dp[i-1][k]==1) dp[i][k]=1;
        else
        {
            if(vec[i-1]==k) dp[i][k]=1;
            else
            {
                if(vec[i-1]>k) dp[i][k]=0;
                else 
                {
                    if(dp[i-1][k-vec[i-1]]) dp[i][k]=1;
                    else dp[i][k]=0;
                }
            }
        }
    }
}

if(dp[n][x])
{
    cout<<1<<" ";
    int idx=-1;

    for(int i=0;i<n;i+=1)
    {
        if(vec[i]%2) {idx=i+1;break;}
    }

    if(idx==-1)
    {
        vector<int> arr;
        for(int i=0;i<n;i+=1)
        {
            for(int j=0;j<=12;j+=1)
            {
                if(vec[i]&(1<<j)) {arr[i]=j;break;}
            }
        }

        int ans=arr[0];
        int mn=1;
        for(int i=1;i<n;i+=1) if(arr[i]<ans) {ans=arr[i];mn=i+1;}
        cout<<mn<<"\n";
    }
    else cout<<idx<<"\n";
}
else cout<<0<<"\n";

}

int main() { fio; int tc=1;//cin>>tc; while(tc--) { solve(); } return 0; }

https://codeforces.com/contest/1516/problem/C //problem name-Baby Ehab Partitions Again i'm constantly getting runtime error on test 6,with exit code 2147483647 can someone please help me correct my code?

 
 
 
 
  • Vote: I like it
  • -26
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

add code in ideone and add link to the blog it will definitely look better !