【codeforces 755F】PolandBall and Gifts

#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define ps push_back
#define fi first
#define se second
#define rei(x) cin >> x
#define pri(x) cout << x
#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 1e6+1000;

int n,k,a[N],b[N],num,cnt,ans1,ans2,w[N];
bool vis[N];
bitset<N> f;

int main()
{
    //freopen("F:\\rush.txt","r",stdin);
    ios::sync_with_stdio(false);
    rei(n),rei(k);
    rep1(i,1,n)
        rei(a[i]);
    rep1(i,1,n)
        if (!vis[i])
        {
            num++,cnt = 0;
            int j = i;
            while (!vis[j])
            {
                vis[j] = true;
                cnt++;
                j = a[j];
            }
            b[num] = cnt;
        }
    n = num;
    sort(b+1,b+1+n);
    int rest = k,t = 0;
    rep1(i,1,n)
    {
        if (b[i]/2<=rest)
        {
            rest-=b[i]/2;
            ans2+=b[i]/2*2;
        }
        else
        {
            ans2+=rest*2;rest = 0;
            break;
        }
        if (b[i]&1) t++;
    }
    ans2+=min(rest,t);
    num = 0;
    rep1(i,1,n)
    {
        int j = i;
        while (j+1<=n && b[j+1]==b[i]) j++;
        int t = 1,len = j-i+1;
        while (len>=t)
        {
            w[++num] = t*b[i];
            len-=t;
            t<<=1;
        }
        if (len)
            w[++num] = len*b[i];
        i = j;
    }
    n = num;
    f[0] = 1;
    rep1(i,1,n)
        f|=f<<(w[i]);
    ans1 = k+1;
    if (f[k])
        ans1 = k;
    pri(ans1<<' '<<ans2<<endl);
    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}