Codeforces 618f double knapsack

Solutions:

It's a wonderful structure of Tao.

Let's suppose that the sum is smaller than the set A.

We regard the set as an array, and sum the prefixes of the two arrays (including position 0);

Then for every sumA[i], there must be a sumB[j], so that 0 ≤ sumA[i] − sumb [i] < n, set to d[i], we can find that j monotonically increases with I.

Note that the last d[i] has n+1 (d[0] to d[n]), while d[i] only has n values (0 to n − 1), so according to the drawer principle, there must be at least two d[i] are the same,
That is, sumA[i] − sumB[j]=sumA[i ′] − sumB[j ′]
(suppose I > I ', then J > J')
The result is: sumA[i] − sumA[i '] = sumB[j] − sumB[j']

So A[i '+ 1] A[i], B[j' + 1] B[j] is the result.

Isn't it wonderful?

#include<bits/stdc++.h>
#define ll long long
using namespace std;  

int getint()
{
    int i=0,f=1;char c;
    for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
    if(c=='-')f=-1,c=getchar();
    for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
    return i*f;
}

const int N=1000005;
int n,a[N],b[N],cnt1,cnt2,st1,ed1,st2,ed2,p[N],vis[N];

void solve(int a[],int b[])
{
    memset(vis,-1,sizeof(vis));
    int i=0,j=0,k,d;
    for(i=0;i<=n;i++)
    {
        while(a[i]-b[j]>=n)j++;
        p[i]=j,d=a[i]-b[j];
        if(vis[d]==-1)vis[d]=i;
        else 
        {
            cnt1=i-vis[d],cnt2=j-p[vis[d]];
            st1=vis[d]+1,ed1=i,st2=p[vis[d]]+1,ed2=j;
            break;
        }
    }
}

int main()
{
    //freopen("lx.in","r",stdin);
    n=getint();
    for(int i=1;i<=n;i++)a[i]=getint()+a[i-1];
    for(int i=1;i<=n;i++)b[i]=getint()+b[i-1];
    if(a[n]<=b[n])solve(a,b);
    else solve(b,a),swap(cnt1,cnt2),swap(st1,st2),swap(ed1,ed2);
    cout<<cnt1<<'\n';
    for(int i=st1;i<=ed1;i++)cout<<i<<' ';
    cout<<'\n';
    cout<<cnt2<<'\n';
    for(int i=st2;i<=ed2;i++)cout<<i<<' ';
    return 0;
}

Added by eruna on Sun, 03 May 2020 17:52:30 +0300