Submission #881970

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
881970	2023-12-02T10:59:15 Z	noyancanturk	Hyper-minimum (IZhO11_hyper)	C++17	100 / 100	432 ms	66132 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	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	2 ms	348 KB	Output is correct
4	Correct	2 ms	604 KB	Output is correct
5	Correct	3 ms	604 KB	Output is correct
6	Correct	12 ms	1628 KB	Output is correct
7	Correct	9 ms	1100 KB	Output is correct
8	Correct	24 ms	1896 KB	Output is correct
9	Correct	42 ms	8272 KB	Output is correct
10	Correct	29 ms	2464 KB	Output is correct
11	Correct	96 ms	8536 KB	Output is correct
12	Correct	192 ms	16208 KB	Output is correct
13	Correct	116 ms	6996 KB	Output is correct
14	Correct	239 ms	32020 KB	Output is correct
15	Correct	351 ms	55536 KB	Output is correct
16	Correct	194 ms	11652 KB	Output is correct
17	Correct	277 ms	22356 KB	Output is correct
18	Correct	432 ms	66132 KB	Output is correct
19	Correct	368 ms	29524 KB	Output is correct
20	Correct	224 ms	13200 KB	Output is correct