oj.uz

Submission #1106421

# Submission time Handle Problem Language Result Execution time Memory
1106421 2024-10-30T10:13:10 Z vjudge1 Vrtić (COCI18_vrtic) C++17
96 / 160
 2000 ms 38660 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 848 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1784 KB Output is correct
2 Correct 507 ms 13304 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 5196 KB Output is correct
2 Execution timed out 2074 ms 37784 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 3680 KB Output is correct
2 Execution timed out 2076 ms 38660 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 7612 KB Output is correct
2 Execution timed out 2075 ms 35808 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 7752 KB Output is correct
2 Execution timed out 2082 ms 35508 KB Time limit exceeded
3 Halted 0 ms 0 KB -