Submission #1106421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106421		vjudge1	Vrtić (COCI18_vrtic)	C++17	96 / 160	2082 ms	38660 KiB

vrtic

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
typedef unsigned long long ull;
const ll N = 160,INF = 2e9;
typedef array<int,2> pr;
typedef array<int,N> vec;
template<typename T>void tomin(T& x,T y){x = min(x,y);}
template<typename T>void tomax(T& x,T y){x = max(x,y);}
//
int n,to[N],pre[N],a[N],vis[N]; vec I;
ull w[N];
int val[N][N],ans[N];

vector<int> buc[N];

mt19937_64 rnd(0);
ull H(vec& arr){ull h = 0; for(int i=1;i<=n;i++)h += w[i] * arr[i]; return h;}

map<ull,int> F;

int dfs(vec now){
    ull h = H(now); if(F.find(h) != F.end())return F[h];
    int& res = F[h]; res = INF;
    int cnt = 0; for(int i=1;i<=n;i++)cnt += now[i] * i;
    if(!cnt)return res = 0;
    for(int i=1;i<=n;i++)if(now[i]){
        vec nxt = now; nxt[i]--;
        tomin(res,max(dfs(nxt),val[n-cnt+1][n-cnt+i]) );
    }
    return res;
}

int dp[N][N]; pr up[N][N];
void calc_dp(int i){
    for(int x=0;x<=n;x++)for(int y=0;y<=n;y++)dp[x][y] = INF;
    dp[i+1][i] = a[i+1] - a[i];
    for(int x=i+1;x<n;x++)for(int y=i;y<x;y++)if(dp[x][y] != INF){
        auto trans = [&](int cx,int cy,int w){
            int nw = max(w,dp[x][y]);
            if(nw < dp[cx][cy]){
                dp[cx][cy] = nw;
                up[cx][cy] = (pr){x,y};
            }
        };
        trans(x+1,y,a[x+1] - a[x]);
        trans(x+1,x,a[x+1] - a[y]);
    }
}

void rdfs(vec now){
    ull h = H(now); ll res = F[h];
    int cnt = 0; for(int i=1;i<=n;i++)cnt += now[i] * i;
    if(!cnt)return;
    for(int i=1;i<=n;i++)if(now[i]){
        vec nxt = now; nxt[i]--;
        if(max(dfs(nxt),val[n-cnt+1][n-cnt+i]) == res){ //还原方案
            rdfs(nxt);
            int u = buc[i].back(); buc[i].pop_back();
            int L = n-cnt+1,R = n-cnt+i;
            if(L == R)ans[u] = a[L];
            else if(L == R-1)ans[u] = a[L],ans[to[u]] = a[R];
            else{
                calc_dp(L);
                int x = -1,y = -1;
                for(int i=L;i<R-1;i++){
                    int w = max(dp[R-1][i],a[R] - a[i]);
                    if(w == val[L][R]){
                        x = R-1,y = i; break;
                    }
                }
                assert(x != -1);
                ans[u] = a[R]; int p = to[u],q = pre[u]; int flag = 0;
                while(1){
                    if(!flag)ans[p] = a[x],p = to[p];
                    else ans[q] = a[x],q = pre[q];
                    if(y == x-1)flag ^= 1;

                    if(x == L+1 && y == L)break;
                    pr tmp = up[x][y];
                    x = tmp[0],y = tmp[1];
                }
                assert(p == q);
                ans[p] = a[L];
            }
            return;
        }
    }
    assert(0);
}


int main(){
    //freopen("apples.in","r",stdin); freopen("apples.out","w",stdout);
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++)w[i] = rnd();
    for(int i=1;i<=n;i++)cin>>to[i],pre[to[i]] = i;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    
    for(int i=1;i<=n;i++)if(!vis[i]){
        int cnt = 0,u = i;
        while(!vis[u])cnt++,vis[u] = 1,u = to[u];
        I[cnt]++;
        buc[cnt].push_back(i);
    }

    for(int i=1;i<n;i++){
        val[i][i+1] = a[i+1] - a[i];
        calc_dp(i);
        for(int j=i+2;j<=n;j++){
            val[i][j] = INF;
            for(int k=i;k<j-1;k++){
                int w = max(dp[j-1][k],a[j] - a[k]);
                tomin(val[i][j],w);
            }
        }
    }

    dfs(I); 
    rdfs(I);

    cout<<F[H(I)]<<endl;
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16