답안 #1106421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1106421	2024-10-30T10:13:10 Z	vjudge1	Vrtić (COCI18_vrtic)	C++17	96 / 160	2000 ms	38660 KB

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.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	592 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	848 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct

Subtask #4
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct

Subtask #5
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct

Subtask #6
16.0 / 16.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #1106421

Compilation message