oj.uz

Submission #957766

# Submission time Handle Problem Language Result Execution time Memory
957766 2024-04-04T09:35:56 Z vjudge1 Mars (APIO22_mars) C++17
14 / 100
 16 ms 20832 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<=4){
                     lx[i][j][k]=i, rx[i][j][k]=i+2*k;
                     ly[i][j][k]=j, ry[i][j][k]=j+2*k;
                 }
             }
        }
    }
    for(int k=n;k>5;k--){
        for(int i=0;i+2*k<2*n+1;i++){
            for(int j=0;j+2*k<2*n+1;j++){
                lx[i][j][k-1]=i, ly[i][j][k-1]=j;
                rx[i][j][k-1]=i+9, ry[i][j][k-1]=j+9;
            }
        }
        for(int i=0;i+2*k-2<2*n+1;i++){
            for(int j=0;j+2*k-2<2*n+1;j++){
                if(!lx[i][j][k-1]){
                    if(max(i, j)+2*k-2 == 2*n+1){
                        rx[i][j][k-1]=i+2*(k-1), ry[i][j][k-1]=j+2*(k-1);
                        lx[i][j][k-1]=rx[i][j][k-1]-9, ly[i][j][k-1]=ry[i][j][k-1]-9;
                    }
                    else{
                        rx[i][j][k-1]=(i*2+2*(k-1))/2+5, ry[i][j][k-1]=(j*2+2*(k-1))/2+5;
                        lx[i][j][k-1]=rx[i][j][k-1]-9, ly[i][j][k-1]=ry[i][j][k-1]-9;
                    }
                }
            }
        }
    }
}

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 20364 KB Output is correct
2 Correct 8 ms 20504 KB Output is correct
3 Correct 8 ms 20184 KB Output is correct
4 Correct 8 ms 20196 KB Output is correct
5 Correct 8 ms 20536 KB Output is correct
6 Correct 8 ms 20832 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20364 KB Output is correct
2 Correct 8 ms 20504 KB Output is correct
3 Correct 8 ms 20184 KB Output is correct
4 Correct 8 ms 20196 KB Output is correct
5 Correct 8 ms 20536 KB Output is correct
6 Correct 8 ms 20832 KB Output is correct
7 Correct 15 ms 19812 KB Output is correct
8 Correct 16 ms 20608 KB Output is correct
9 Correct 16 ms 20632 KB Output is correct
10 Correct 15 ms 19880 KB Output is correct
11 Correct 14 ms 20740 KB Output is correct
12 Correct 15 ms 20468 KB Output is correct
13 Correct 14 ms 20252 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20364 KB Output is correct
2 Correct 8 ms 20504 KB Output is correct
3 Correct 8 ms 20184 KB Output is correct
4 Correct 8 ms 20196 KB Output is correct
5 Correct 8 ms 20536 KB Output is correct
6 Correct 8 ms 20832 KB Output is correct
7 Correct 15 ms 19812 KB Output is correct
8 Correct 16 ms 20608 KB Output is correct
9 Correct 16 ms 20632 KB Output is correct
10 Correct 15 ms 19880 KB Output is correct
11 Correct 14 ms 20740 KB Output is correct
12 Correct 15 ms 20468 KB Output is correct
13 Correct 14 ms 20252 KB Output is correct
14 Incorrect 3 ms 2684 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20364 KB Output is correct
2 Correct 8 ms 20504 KB Output is correct
3 Correct 8 ms 20184 KB Output is correct
4 Correct 8 ms 20196 KB Output is correct
5 Correct 8 ms 20536 KB Output is correct
6 Correct 8 ms 20832 KB Output is correct
7 Correct 15 ms 19812 KB Output is correct
8 Correct 16 ms 20608 KB Output is correct
9 Correct 16 ms 20632 KB Output is correct
10 Correct 15 ms 19880 KB Output is correct
11 Correct 14 ms 20740 KB Output is correct
12 Correct 15 ms 20468 KB Output is correct
13 Correct 14 ms 20252 KB Output is correct
14 Incorrect 3 ms 2684 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20364 KB Output is correct
2 Correct 8 ms 20504 KB Output is correct
3 Correct 8 ms 20184 KB Output is correct
4 Correct 8 ms 20196 KB Output is correct
5 Correct 8 ms 20536 KB Output is correct
6 Correct 8 ms 20832 KB Output is correct
7 Correct 15 ms 19812 KB Output is correct
8 Correct 16 ms 20608 KB Output is correct
9 Correct 16 ms 20632 KB Output is correct
10 Correct 15 ms 19880 KB Output is correct
11 Correct 14 ms 20740 KB Output is correct
12 Correct 15 ms 20468 KB Output is correct
13 Correct 14 ms 20252 KB Output is correct
14 Incorrect 3 ms 2684 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20364 KB Output is correct
2 Correct 8 ms 20504 KB Output is correct
3 Correct 8 ms 20184 KB Output is correct
4 Correct 8 ms 20196 KB Output is correct
5 Correct 8 ms 20536 KB Output is correct
6 Correct 8 ms 20832 KB Output is correct
7 Correct 15 ms 19812 KB Output is correct
8 Correct 16 ms 20608 KB Output is correct
9 Correct 16 ms 20632 KB Output is correct
10 Correct 15 ms 19880 KB Output is correct
11 Correct 14 ms 20740 KB Output is correct
12 Correct 15 ms 20468 KB Output is correct
13 Correct 14 ms 20252 KB Output is correct
14 Incorrect 3 ms 2684 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20364 KB Output is correct
2 Correct 8 ms 20504 KB Output is correct
3 Correct 8 ms 20184 KB Output is correct
4 Correct 8 ms 20196 KB Output is correct
5 Correct 8 ms 20536 KB Output is correct
6 Correct 8 ms 20832 KB Output is correct
7 Correct 15 ms 19812 KB Output is correct
8 Correct 16 ms 20608 KB Output is correct
9 Correct 16 ms 20632 KB Output is correct
10 Correct 15 ms 19880 KB Output is correct
11 Correct 14 ms 20740 KB Output is correct
12 Correct 15 ms 20468 KB Output is correct
13 Correct 14 ms 20252 KB Output is correct
14 Incorrect 3 ms 2684 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20364 KB Output is correct
2 Correct 8 ms 20504 KB Output is correct
3 Correct 8 ms 20184 KB Output is correct
4 Correct 8 ms 20196 KB Output is correct
5 Correct 8 ms 20536 KB Output is correct
6 Correct 8 ms 20832 KB Output is correct
7 Correct 15 ms 19812 KB Output is correct
8 Correct 16 ms 20608 KB Output is correct
9 Correct 16 ms 20632 KB Output is correct
10 Correct 15 ms 19880 KB Output is correct
11 Correct 14 ms 20740 KB Output is correct
12 Correct 15 ms 20468 KB Output is correct
13 Correct 14 ms 20252 KB Output is correct
14 Incorrect 3 ms 2684 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20364 KB Output is correct
2 Correct 8 ms 20504 KB Output is correct
3 Correct 8 ms 20184 KB Output is correct
4 Correct 8 ms 20196 KB Output is correct
5 Correct 8 ms 20536 KB Output is correct
6 Correct 8 ms 20832 KB Output is correct
7 Correct 15 ms 19812 KB Output is correct
8 Correct 16 ms 20608 KB Output is correct
9 Correct 16 ms 20632 KB Output is correct
10 Correct 15 ms 19880 KB Output is correct
11 Correct 14 ms 20740 KB Output is correct
12 Correct 15 ms 20468 KB Output is correct
13 Correct 14 ms 20252 KB Output is correct
14 Incorrect 3 ms 2684 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20364 KB Output is correct
2 Correct 8 ms 20504 KB Output is correct
3 Correct 8 ms 20184 KB Output is correct
4 Correct 8 ms 20196 KB Output is correct
5 Correct 8 ms 20536 KB Output is correct
6 Correct 8 ms 20832 KB Output is correct
7 Correct 15 ms 19812 KB Output is correct
8 Correct 16 ms 20608 KB Output is correct
9 Correct 16 ms 20632 KB Output is correct
10 Correct 15 ms 19880 KB Output is correct
11 Correct 14 ms 20740 KB Output is correct
12 Correct 15 ms 20468 KB Output is correct
13 Correct 14 ms 20252 KB Output is correct
14 Incorrect 3 ms 2684 KB Incorrect
15 Halted 0 ms 0 KB -