Submission #4433378

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int NOEL(){
    cout<<0<<endl;
    return 0;
}
ll gcd(ll a,ll b){if(a<b)swap(a,b);return (b?gcd(a%b,b):a);}
#define N 10010
class KnapSack{
    public:
    vector<ll> res;
    bool d[N];
    bool main(vector<ll> w,ll key){//in total O(N√N)
	for(int i=0;i<=key;i++)d[i]=0; d[0]=1;
	for(auto x:w)for(int i=0;i+x<=key;i++)d[i+x]|=d[i];
	if(d[key]==0)return 0;
	res.clear();
	for(ll p=0;p<w.size();p++){
	    while(1){
		if(key-w[p]>=0&&d[key-w[p]]){
		    key-=w[p];
		    res.push_back(w[p]);
		}
		else break;
	    }
	}
	return 1;
    }
};KnapSack knapsack;
struct component{
  vector<ll> t;  
};
vector<component> cycle[N];
ll n,k,a[N],ans[N];
bool used[N];
vector<ll> wei[N]; 
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){cin>>a[i]; used[i]=0;}
    for(int i=1;i<=n;i++){
	if(used[i])continue;
	ll x=i; component com;
	while(1){
	    used[x]=1;
	    com.t.push_back(x);
	    x=a[x];
	    if(x==i)break;
	}
	cycle[com.t.size()].push_back(com);
    }
    for(int i=1;i<=n;i++){
	ll c=gcd(i,k);
	wei[i/c].push_back(c);
    }
    for(ll i=0;i<N;i++){
	if(cycle[i].size()==0)continue;
	if(knapsack.main(wei[i],cycle[i].size())==0)return NOEL();
	ll p=0;
	for(auto len:knapsack.res){//cout<<len<<",";
	    ll dat[N];
	    ll mid=0;
	    for(int e=0;e<i;e++){
		dat[mid]=e;
		mid=(mid+k%(i*len)/len)%i;
	    }
	    for(int e=0;e<i;e++){
		for(int j=0;j<len-1;j++){
		    ans[cycle[i][p+j].t[dat[e]]]=cycle[i][p+j+1].t[dat[e]];
		}
		ans[cycle[i][p+len-1].t[dat[e]]]=cycle[i][p].t[dat[(e+1)%i]];
	    }
	    p+=len;
	}
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
    return 0;
}

Submission Info

Judge Result