oj.uz

Submission #957710

# Submission time Handle Problem Language Result Execution time Memory
957710 2024-04-04T08:34:20 Z vjudge1 Mars (APIO22_mars) C++17
21 / 100
 193 ms 21864 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
//#define int long long

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

const int dx[]={-1, 1, 0, 0, 0};
const int dy[]={0, 0, 1, -1, 0};
typedef long long ll;
using namespace std;
const int mx=50+12;
const int mod=998244353;
const bool T=1;

int used[mx][mx];
int lx[mx][mx][mx], rx[mx][mx][mx];
int ly[mx][mx][mx], ry[mx][mx][mx];

int pos(int x,int y,int n){
    return x*n+y;
}

void dfs(int x,int y,int n){
    used[x][y]=1;
    for(int i=0;i<4;i++){
        int x1=dx[i]+x, y1=dy[i]+y;
        if(min(x1, y1)>=0 && max(x1, y1)<n && !used[x1][y1]){
            dfs(x1, y1, n);
        }
    }
}

void init(int n){
    for(int i=0;i<2*n+1;i++){
        for(int j=0;j<2*n+1;j++){
             for(int k=0;k<=n;k++){
                 lx[i][j][k]=rx[i][j][k]=-1;
                 ly[i][j][k]=ry[i][j][k]=-1;
                 if(!k){
                     lx[i][j][k]=rx[i][j][k]=i;
                     ly[i][j][k]=ry[i][j][k]=j;
                 }
             }
        }
    }
    for(int k=n;k;k--){
        for(int i=0;i+2*k<2*n+1;i++){
            for(int j=0;j+2*k<2*n+1;j++){
                for(int x=i;x<i+2*k+1;x++){
                    for(int y=j;y<j+2*k+1;y++){
                        used[x][y]=0;
                    }
                }
                for(int x=i;x<=i+2;x++){
                    for(int y=j;y<=j+2;y++){
                        if(lx[x][y][k-1]!=-1){
                            for(int l=lx[x][y][k-1];l<=rx[x][y][k-1];l++){
                                for(int r=ly[x][y][k-1];r<=ry[x][y][k-1];r++){
                                    used[l][r]=1;
                                }
                            }
                        }
                    }
                }
                for(int x=i;x<=i+2;x++){
                    for(int y=j;y<=j+2;y++){
                        if(lx[x][y][k-1]!=-1){
                            continue;
                        }
                        int fx=-1,fy=-1;
                        for(int x1=i;x1<x+2*k-1;x1++){
                            for(int y1=j;y1<y+2*k-1;y1++){
                                if(!used[x1][y1]){
                                    fx=x1, fy=y1;
                                    break;
                                }
                            }
                            if(fx!=-1)break;
                        }
                        if(fx==-1 && fy==-1){
                            continue;
                        }
                        else{
                            lx[x][y][k-1]=fx, ly[x][y][k-1]=fy;
                            rx[x][y][k-1]=min(fx+9, x+2*k-2), ry[x][y][k-1]=min(fy+9, y+2*k-2);
                            while(rx[x][y][k-1]-lx[x][y][k-1]<9 && lx[x][y][k-1]>x){
                                lx[x][y][k-1]--;
                            }
                            while(ry[x][y][k-1]-ly[x][y][k-1]<9 && ly[x][y][k-1]>y){
                                ly[x][y][k-1]--;
                            }
                        }
                        for(int l=lx[x][y][k-1];l<=rx[x][y][k-1];l++){
                            for(int r=ly[x][y][k-1];r<=ry[x][y][k-1];r++){
                                used[l][r]=1;
                            }
                        }
                    }
                }
                for(int x=i;x<i+2*k+1;x++){
                    for(int y=j;y<j+2*k+1;y++){
                        if(!used[x][y]){
                            cout<<"! "<<i<<' '<<j<<' '<<k<<endl;
                            cout<<"find "<<x<<' '<<y<<endl;
                            assert(0);
                        }
                    }
                }
            }
        }
    }
}

void upd(string a, int x,int y, int k){
    if(lx[x][y][k]==-1){
        return;
    }
    int pos=0;
    for(int i=lx[x][y][k];i<=rx[x][y][k];i++){
        for(int j=ly[x][y][k];j<=ry[x][y][k];j++){
            used[i][j]=(a[pos] == '1');
            pos++;
        }
    }
}

std::string process(std::vector<std::vector<std::string> > a,int x,int y,int k,int n){
    init(n);
    k++;
    string ans="";
    while(ans.size()<100){
        ans+='0';
    }
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            upd(a[i][j], x+i, y+j, k-1);
        }
    }
    if(lx[x][y][k]!=-1){
        int pos=0;
        for(int i=lx[x][y][k];i<=rx[x][y][k];i++){
            for(int j=ly[x][y][k];j<=ry[x][y][k];j++){
                ans[pos]=used[i][j]+'0';
                pos++;
            }
        }
    }
    if(n==k){
        for(int i=0;i<2*n+1;i++){
            for(int j=0;j<2*n+1;j++){
                used[i][j]=1-used[i][j];
            }
        }
        int cnt=0;
        for(int i=0;i<2*n+1;i++){
            for(int j=0;j<2*n+1;j++){
                if(!used[i][j]){
                    cnt++;
                    dfs(i, j, 2*n+1);
                }
            }
        }
        for(int i=0;i<100;i++){
            if(i>=20){
                ans[i]='0';
            }
            else{
                if((cnt&(1<<i))){
                    ans[i]='1';
                }
                else{
                    ans[i]='0';
                }
            }
        }
        return ans;
    }
    return ans;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20940 KB Output is correct
3 Correct 8 ms 20352 KB Output is correct
4 Correct 8 ms 20504 KB Output is correct
5 Correct 8 ms 20356 KB Output is correct
6 Correct 8 ms 20264 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20940 KB Output is correct
3 Correct 8 ms 20352 KB Output is correct
4 Correct 8 ms 20504 KB Output is correct
5 Correct 8 ms 20356 KB Output is correct
6 Correct 8 ms 20264 KB Output is correct
7 Correct 16 ms 20508 KB Output is correct
8 Correct 24 ms 20320 KB Output is correct
9 Correct 23 ms 20800 KB Output is correct
10 Correct 23 ms 20104 KB Output is correct
11 Correct 24 ms 20032 KB Output is correct
12 Correct 23 ms 20600 KB Output is correct
13 Correct 22 ms 20668 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20940 KB Output is correct
3 Correct 8 ms 20352 KB Output is correct
4 Correct 8 ms 20504 KB Output is correct
5 Correct 8 ms 20356 KB Output is correct
6 Correct 8 ms 20264 KB Output is correct
7 Correct 16 ms 20508 KB Output is correct
8 Correct 24 ms 20320 KB Output is correct
9 Correct 23 ms 20800 KB Output is correct
10 Correct 23 ms 20104 KB Output is correct
11 Correct 24 ms 20032 KB Output is correct
12 Correct 23 ms 20600 KB Output is correct
13 Correct 22 ms 20668 KB Output is correct
14 Correct 89 ms 21372 KB Output is correct
15 Correct 180 ms 21436 KB Output is correct
16 Correct 179 ms 21428 KB Output is correct
17 Correct 192 ms 21864 KB Output is correct
18 Correct 179 ms 21592 KB Output is correct
19 Correct 183 ms 21560 KB Output is correct
20 Correct 193 ms 21556 KB Output is correct

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20940 KB Output is correct
3 Correct 8 ms 20352 KB Output is correct
4 Correct 8 ms 20504 KB Output is correct
5 Correct 8 ms 20356 KB Output is correct
6 Correct 8 ms 20264 KB Output is correct
7 Correct 16 ms 20508 KB Output is correct
8 Correct 24 ms 20320 KB Output is correct
9 Correct 23 ms 20800 KB Output is correct
10 Correct 23 ms 20104 KB Output is correct
11 Correct 24 ms 20032 KB Output is correct
12 Correct 23 ms 20600 KB Output is correct
13 Correct 22 ms 20668 KB Output is correct
14 Correct 89 ms 21372 KB Output is correct
15 Correct 180 ms 21436 KB Output is correct
16 Correct 179 ms 21428 KB Output is correct
17 Correct 192 ms 21864 KB Output is correct
18 Correct 179 ms 21592 KB Output is correct
19 Correct 183 ms 21560 KB Output is correct
20 Correct 193 ms 21556 KB Output is correct
21 Runtime error 3 ms 4952 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20940 KB Output is correct
3 Correct 8 ms 20352 KB Output is correct
4 Correct 8 ms 20504 KB Output is correct
5 Correct 8 ms 20356 KB Output is correct
6 Correct 8 ms 20264 KB Output is correct
7 Correct 16 ms 20508 KB Output is correct
8 Correct 24 ms 20320 KB Output is correct
9 Correct 23 ms 20800 KB Output is correct
10 Correct 23 ms 20104 KB Output is correct
11 Correct 24 ms 20032 KB Output is correct
12 Correct 23 ms 20600 KB Output is correct
13 Correct 22 ms 20668 KB Output is correct
14 Correct 89 ms 21372 KB Output is correct
15 Correct 180 ms 21436 KB Output is correct
16 Correct 179 ms 21428 KB Output is correct
17 Correct 192 ms 21864 KB Output is correct
18 Correct 179 ms 21592 KB Output is correct
19 Correct 183 ms 21560 KB Output is correct
20 Correct 193 ms 21556 KB Output is correct
21 Runtime error 3 ms 4952 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20940 KB Output is correct
3 Correct 8 ms 20352 KB Output is correct
4 Correct 8 ms 20504 KB Output is correct
5 Correct 8 ms 20356 KB Output is correct
6 Correct 8 ms 20264 KB Output is correct
7 Correct 16 ms 20508 KB Output is correct
8 Correct 24 ms 20320 KB Output is correct
9 Correct 23 ms 20800 KB Output is correct
10 Correct 23 ms 20104 KB Output is correct
11 Correct 24 ms 20032 KB Output is correct
12 Correct 23 ms 20600 KB Output is correct
13 Correct 22 ms 20668 KB Output is correct
14 Correct 89 ms 21372 KB Output is correct
15 Correct 180 ms 21436 KB Output is correct
16 Correct 179 ms 21428 KB Output is correct
17 Correct 192 ms 21864 KB Output is correct
18 Correct 179 ms 21592 KB Output is correct
19 Correct 183 ms 21560 KB Output is correct
20 Correct 193 ms 21556 KB Output is correct
21 Runtime error 3 ms 4952 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20940 KB Output is correct
3 Correct 8 ms 20352 KB Output is correct
4 Correct 8 ms 20504 KB Output is correct
5 Correct 8 ms 20356 KB Output is correct
6 Correct 8 ms 20264 KB Output is correct
7 Correct 16 ms 20508 KB Output is correct
8 Correct 24 ms 20320 KB Output is correct
9 Correct 23 ms 20800 KB Output is correct
10 Correct 23 ms 20104 KB Output is correct
11 Correct 24 ms 20032 KB Output is correct
12 Correct 23 ms 20600 KB Output is correct
13 Correct 22 ms 20668 KB Output is correct
14 Correct 89 ms 21372 KB Output is correct
15 Correct 180 ms 21436 KB Output is correct
16 Correct 179 ms 21428 KB Output is correct
17 Correct 192 ms 21864 KB Output is correct
18 Correct 179 ms 21592 KB Output is correct
19 Correct 183 ms 21560 KB Output is correct
20 Correct 193 ms 21556 KB Output is correct
21 Runtime error 3 ms 4952 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20940 KB Output is correct
3 Correct 8 ms 20352 KB Output is correct
4 Correct 8 ms 20504 KB Output is correct
5 Correct 8 ms 20356 KB Output is correct
6 Correct 8 ms 20264 KB Output is correct
7 Correct 16 ms 20508 KB Output is correct
8 Correct 24 ms 20320 KB Output is correct
9 Correct 23 ms 20800 KB Output is correct
10 Correct 23 ms 20104 KB Output is correct
11 Correct 24 ms 20032 KB Output is correct
12 Correct 23 ms 20600 KB Output is correct
13 Correct 22 ms 20668 KB Output is correct
14 Correct 89 ms 21372 KB Output is correct
15 Correct 180 ms 21436 KB Output is correct
16 Correct 179 ms 21428 KB Output is correct
17 Correct 192 ms 21864 KB Output is correct
18 Correct 179 ms 21592 KB Output is correct
19 Correct 183 ms 21560 KB Output is correct
20 Correct 193 ms 21556 KB Output is correct
21 Runtime error 3 ms 4952 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20940 KB Output is correct
3 Correct 8 ms 20352 KB Output is correct
4 Correct 8 ms 20504 KB Output is correct
5 Correct 8 ms 20356 KB Output is correct
6 Correct 8 ms 20264 KB Output is correct
7 Correct 16 ms 20508 KB Output is correct
8 Correct 24 ms 20320 KB Output is correct
9 Correct 23 ms 20800 KB Output is correct
10 Correct 23 ms 20104 KB Output is correct
11 Correct 24 ms 20032 KB Output is correct
12 Correct 23 ms 20600 KB Output is correct
13 Correct 22 ms 20668 KB Output is correct
14 Correct 89 ms 21372 KB Output is correct
15 Correct 180 ms 21436 KB Output is correct
16 Correct 179 ms 21428 KB Output is correct
17 Correct 192 ms 21864 KB Output is correct
18 Correct 179 ms 21592 KB Output is correct
19 Correct 183 ms 21560 KB Output is correct
20 Correct 193 ms 21556 KB Output is correct
21 Runtime error 3 ms 4952 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20940 KB Output is correct
3 Correct 8 ms 20352 KB Output is correct
4 Correct 8 ms 20504 KB Output is correct
5 Correct 8 ms 20356 KB Output is correct
6 Correct 8 ms 20264 KB Output is correct
7 Correct 16 ms 20508 KB Output is correct
8 Correct 24 ms 20320 KB Output is correct
9 Correct 23 ms 20800 KB Output is correct
10 Correct 23 ms 20104 KB Output is correct
11 Correct 24 ms 20032 KB Output is correct
12 Correct 23 ms 20600 KB Output is correct
13 Correct 22 ms 20668 KB Output is correct
14 Correct 89 ms 21372 KB Output is correct
15 Correct 180 ms 21436 KB Output is correct
16 Correct 179 ms 21428 KB Output is correct
17 Correct 192 ms 21864 KB Output is correct
18 Correct 179 ms 21592 KB Output is correct
19 Correct 183 ms 21560 KB Output is correct
20 Correct 193 ms 21556 KB Output is correct
21 Runtime error 3 ms 4952 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -