Submission #881969

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
881969	2023-12-02T10:58:17 Z	vjudge1	Hyper-minimum (IZhO11_hyper)	C++17	100 / 100	440 ms	81280 KB

hyper

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=1.5e6+100;
#else
    const int lim=3e3;
#endif

#include "bits/stdc++.h"
using namespace std;

#define int long long
#define pb push_back

const int mod=1e9+7;
using pii=pair<int,int>;

void solve(){
    int n,m;
    cin>>n>>m;
    int nm=n-m+1;
    int a[n][n][n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                for(int l=0;l<n;l++){
                    cin>>a[i][j][k][l];
                }
            }
        }
    }
    int b[n][n][n][nm];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                multiset<int>sety;
                for(int l=0;l<m;l++){
                    sety.insert(a[i][j][k][l]);
                }
                b[i][j][k][0]=*sety.begin();
                for(int l=1;l<nm;l++){
                    sety.erase(sety.find(a[i][j][k][l-1]));
                    sety.insert(a[i][j][k][l+m-1]);
                    b[i][j][k][l]=*sety.begin();
                }
            }
        }
    }
    int c[n][n][nm][nm];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int l=0;l<nm;l++){
                multiset<int>sety;
                for(int k=0;k<m;k++){
                    sety.insert(b[i][j][k][l]);
                }
                c[i][j][0][l]=*sety.begin();
                for(int k=1;k<nm;k++){
                    sety.erase(sety.find(b[i][j][k-1][l]));
                    sety.insert(b[i][j][k+m-1][l]);
                    c[i][j][k][l]=*sety.begin();
                }
            }
        }
    }
    int d[n][nm][nm][nm];
    for(int i=0;i<n;i++){
        for(int k=0;k<nm;k++){
            for(int l=0;l<nm;l++){
                multiset<int>sety;
                for(int j=0;j<m;j++){
                    sety.insert(c[i][j][k][l]);
                }
                d[i][0][k][l]=*sety.begin();
                for(int j=1;j<nm;j++){
                    sety.erase(sety.find(c[i][j-1][k][l]));
                    sety.insert(c[i][j+m-1][k][l]);
                    d[i][j][k][l]=*sety.begin();
                }
            }
        }
    }
    int ans[nm][nm][nm][nm];
    for(int j=0;j<nm;j++){
        for(int k=0;k<nm;k++){
            for(int l=0;l<nm;l++){
                multiset<int>sety;
                for(int i=0;i<m;i++){
                    sety.insert(d[i][j][k][l]);
                }
                ans[0][j][k][l]=*sety.begin();
                for(int i=1;i<nm;i++){
                    sety.erase(sety.find(d[i-1][j][k][l]));
                    sety.insert(d[i+m-1][j][k][l]);
                    ans[i][j][k][l]=*sety.begin();
                }
            }
        }
    }
    for(int i=0;i<nm;i++){
        for(int j=0;j<nm;j++){
            for(int k=0;k<nm;k++){
                for(int l=0;l<nm;l++){
                    cout<<ans[i][j][k][l]<<" ";
                }
            }
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	2 ms	604 KB	Output is correct
4	Correct	2 ms	604 KB	Output is correct
5	Correct	3 ms	636 KB	Output is correct
6	Correct	12 ms	2140 KB	Output is correct
7	Correct	11 ms	1880 KB	Output is correct
8	Correct	25 ms	3408 KB	Output is correct
9	Correct	42 ms	9872 KB	Output is correct
10	Correct	30 ms	3924 KB	Output is correct
11	Correct	98 ms	12572 KB	Output is correct
12	Correct	206 ms	24656 KB	Output is correct
13	Correct	119 ms	15444 KB	Output is correct
14	Correct	223 ms	40440 KB	Output is correct
15	Correct	353 ms	67668 KB	Output is correct
16	Correct	193 ms	23908 KB	Output is correct
17	Correct	282 ms	34388 KB	Output is correct
18	Correct	440 ms	81280 KB	Output is correct
19	Correct	369 ms	44760 KB	Output is correct
20	Correct	226 ms	28468 KB	Output is correct