oj.uz

Submission #957765

# Submission time Handle Problem Language Result Execution time Memory
957765 2024-04-04T09:33:17 Z vjudge1 Mars (APIO22_mars) C++17
14 / 100
 16 ms 21232 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+4, ry[i][j][k-1]=(j*2+2*(k-1))/2+4;
                        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 20164 KB Output is correct
2 Correct 14 ms 20276 KB Output is correct
3 Correct 8 ms 20348 KB Output is correct
4 Correct 8 ms 20576 KB Output is correct
5 Correct 8 ms 20112 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20164 KB Output is correct
2 Correct 14 ms 20276 KB Output is correct
3 Correct 8 ms 20348 KB Output is correct
4 Correct 8 ms 20576 KB Output is correct
5 Correct 8 ms 20112 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 11 ms 20028 KB Output is correct
8 Correct 16 ms 20212 KB Output is correct
9 Correct 15 ms 20264 KB Output is correct
10 Correct 16 ms 20188 KB Output is correct
11 Correct 16 ms 20512 KB Output is correct
12 Correct 15 ms 20832 KB Output is correct
13 Correct 13 ms 21232 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20164 KB Output is correct
2 Correct 14 ms 20276 KB Output is correct
3 Correct 8 ms 20348 KB Output is correct
4 Correct 8 ms 20576 KB Output is correct
5 Correct 8 ms 20112 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 11 ms 20028 KB Output is correct
8 Correct 16 ms 20212 KB Output is correct
9 Correct 15 ms 20264 KB Output is correct
10 Correct 16 ms 20188 KB Output is correct
11 Correct 16 ms 20512 KB Output is correct
12 Correct 15 ms 20832 KB Output is correct
13 Correct 13 ms 21232 KB Output is correct
14 Incorrect 3 ms 2688 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20164 KB Output is correct
2 Correct 14 ms 20276 KB Output is correct
3 Correct 8 ms 20348 KB Output is correct
4 Correct 8 ms 20576 KB Output is correct
5 Correct 8 ms 20112 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 11 ms 20028 KB Output is correct
8 Correct 16 ms 20212 KB Output is correct
9 Correct 15 ms 20264 KB Output is correct
10 Correct 16 ms 20188 KB Output is correct
11 Correct 16 ms 20512 KB Output is correct
12 Correct 15 ms 20832 KB Output is correct
13 Correct 13 ms 21232 KB Output is correct
14 Incorrect 3 ms 2688 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20164 KB Output is correct
2 Correct 14 ms 20276 KB Output is correct
3 Correct 8 ms 20348 KB Output is correct
4 Correct 8 ms 20576 KB Output is correct
5 Correct 8 ms 20112 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 11 ms 20028 KB Output is correct
8 Correct 16 ms 20212 KB Output is correct
9 Correct 15 ms 20264 KB Output is correct
10 Correct 16 ms 20188 KB Output is correct
11 Correct 16 ms 20512 KB Output is correct
12 Correct 15 ms 20832 KB Output is correct
13 Correct 13 ms 21232 KB Output is correct
14 Incorrect 3 ms 2688 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20164 KB Output is correct
2 Correct 14 ms 20276 KB Output is correct
3 Correct 8 ms 20348 KB Output is correct
4 Correct 8 ms 20576 KB Output is correct
5 Correct 8 ms 20112 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 11 ms 20028 KB Output is correct
8 Correct 16 ms 20212 KB Output is correct
9 Correct 15 ms 20264 KB Output is correct
10 Correct 16 ms 20188 KB Output is correct
11 Correct 16 ms 20512 KB Output is correct
12 Correct 15 ms 20832 KB Output is correct
13 Correct 13 ms 21232 KB Output is correct
14 Incorrect 3 ms 2688 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20164 KB Output is correct
2 Correct 14 ms 20276 KB Output is correct
3 Correct 8 ms 20348 KB Output is correct
4 Correct 8 ms 20576 KB Output is correct
5 Correct 8 ms 20112 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 11 ms 20028 KB Output is correct
8 Correct 16 ms 20212 KB Output is correct
9 Correct 15 ms 20264 KB Output is correct
10 Correct 16 ms 20188 KB Output is correct
11 Correct 16 ms 20512 KB Output is correct
12 Correct 15 ms 20832 KB Output is correct
13 Correct 13 ms 21232 KB Output is correct
14 Incorrect 3 ms 2688 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20164 KB Output is correct
2 Correct 14 ms 20276 KB Output is correct
3 Correct 8 ms 20348 KB Output is correct
4 Correct 8 ms 20576 KB Output is correct
5 Correct 8 ms 20112 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 11 ms 20028 KB Output is correct
8 Correct 16 ms 20212 KB Output is correct
9 Correct 15 ms 20264 KB Output is correct
10 Correct 16 ms 20188 KB Output is correct
11 Correct 16 ms 20512 KB Output is correct
12 Correct 15 ms 20832 KB Output is correct
13 Correct 13 ms 21232 KB Output is correct
14 Incorrect 3 ms 2688 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20164 KB Output is correct
2 Correct 14 ms 20276 KB Output is correct
3 Correct 8 ms 20348 KB Output is correct
4 Correct 8 ms 20576 KB Output is correct
5 Correct 8 ms 20112 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 11 ms 20028 KB Output is correct
8 Correct 16 ms 20212 KB Output is correct
9 Correct 15 ms 20264 KB Output is correct
10 Correct 16 ms 20188 KB Output is correct
11 Correct 16 ms 20512 KB Output is correct
12 Correct 15 ms 20832 KB Output is correct
13 Correct 13 ms 21232 KB Output is correct
14 Incorrect 3 ms 2688 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20164 KB Output is correct
2 Correct 14 ms 20276 KB Output is correct
3 Correct 8 ms 20348 KB Output is correct
4 Correct 8 ms 20576 KB Output is correct
5 Correct 8 ms 20112 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 11 ms 20028 KB Output is correct
8 Correct 16 ms 20212 KB Output is correct
9 Correct 15 ms 20264 KB Output is correct
10 Correct 16 ms 20188 KB Output is correct
11 Correct 16 ms 20512 KB Output is correct
12 Correct 15 ms 20832 KB Output is correct
13 Correct 13 ms 21232 KB Output is correct
14 Incorrect 3 ms 2688 KB Incorrect
15 Halted 0 ms 0 KB -