oj.uz

Submission #957733

# Submission time Handle Problem Language Result Execution time Memory
957733 2024-04-04T08:59:01 Z vjudge1 Mars (APIO22_mars) C++17
14 / 100
 16 ms 20760 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]){
                    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;
                }
            }
        }
    }
}

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 20412 KB Output is correct
2 Correct 8 ms 20760 KB Output is correct
3 Correct 8 ms 20668 KB Output is correct
4 Correct 8 ms 20412 KB Output is correct
5 Correct 7 ms 20616 KB Output is correct
6 Correct 8 ms 20096 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20412 KB Output is correct
2 Correct 8 ms 20760 KB Output is correct
3 Correct 8 ms 20668 KB Output is correct
4 Correct 8 ms 20412 KB Output is correct
5 Correct 7 ms 20616 KB Output is correct
6 Correct 8 ms 20096 KB Output is correct
7 Correct 11 ms 20348 KB Output is correct
8 Correct 15 ms 20516 KB Output is correct
9 Correct 16 ms 20300 KB Output is correct
10 Correct 16 ms 20512 KB Output is correct
11 Correct 15 ms 20032 KB Output is correct
12 Correct 13 ms 20260 KB Output is correct
13 Correct 15 ms 19776 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20412 KB Output is correct
2 Correct 8 ms 20760 KB Output is correct
3 Correct 8 ms 20668 KB Output is correct
4 Correct 8 ms 20412 KB Output is correct
5 Correct 7 ms 20616 KB Output is correct
6 Correct 8 ms 20096 KB Output is correct
7 Correct 11 ms 20348 KB Output is correct
8 Correct 15 ms 20516 KB Output is correct
9 Correct 16 ms 20300 KB Output is correct
10 Correct 16 ms 20512 KB Output is correct
11 Correct 15 ms 20032 KB Output is correct
12 Correct 13 ms 20260 KB Output is correct
13 Correct 15 ms 19776 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 20412 KB Output is correct
2 Correct 8 ms 20760 KB Output is correct
3 Correct 8 ms 20668 KB Output is correct
4 Correct 8 ms 20412 KB Output is correct
5 Correct 7 ms 20616 KB Output is correct
6 Correct 8 ms 20096 KB Output is correct
7 Correct 11 ms 20348 KB Output is correct
8 Correct 15 ms 20516 KB Output is correct
9 Correct 16 ms 20300 KB Output is correct
10 Correct 16 ms 20512 KB Output is correct
11 Correct 15 ms 20032 KB Output is correct
12 Correct 13 ms 20260 KB Output is correct
13 Correct 15 ms 19776 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 20412 KB Output is correct
2 Correct 8 ms 20760 KB Output is correct
3 Correct 8 ms 20668 KB Output is correct
4 Correct 8 ms 20412 KB Output is correct
5 Correct 7 ms 20616 KB Output is correct
6 Correct 8 ms 20096 KB Output is correct
7 Correct 11 ms 20348 KB Output is correct
8 Correct 15 ms 20516 KB Output is correct
9 Correct 16 ms 20300 KB Output is correct
10 Correct 16 ms 20512 KB Output is correct
11 Correct 15 ms 20032 KB Output is correct
12 Correct 13 ms 20260 KB Output is correct
13 Correct 15 ms 19776 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 20412 KB Output is correct
2 Correct 8 ms 20760 KB Output is correct
3 Correct 8 ms 20668 KB Output is correct
4 Correct 8 ms 20412 KB Output is correct
5 Correct 7 ms 20616 KB Output is correct
6 Correct 8 ms 20096 KB Output is correct
7 Correct 11 ms 20348 KB Output is correct
8 Correct 15 ms 20516 KB Output is correct
9 Correct 16 ms 20300 KB Output is correct
10 Correct 16 ms 20512 KB Output is correct
11 Correct 15 ms 20032 KB Output is correct
12 Correct 13 ms 20260 KB Output is correct
13 Correct 15 ms 19776 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 20412 KB Output is correct
2 Correct 8 ms 20760 KB Output is correct
3 Correct 8 ms 20668 KB Output is correct
4 Correct 8 ms 20412 KB Output is correct
5 Correct 7 ms 20616 KB Output is correct
6 Correct 8 ms 20096 KB Output is correct
7 Correct 11 ms 20348 KB Output is correct
8 Correct 15 ms 20516 KB Output is correct
9 Correct 16 ms 20300 KB Output is correct
10 Correct 16 ms 20512 KB Output is correct
11 Correct 15 ms 20032 KB Output is correct
12 Correct 13 ms 20260 KB Output is correct
13 Correct 15 ms 19776 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 20412 KB Output is correct
2 Correct 8 ms 20760 KB Output is correct
3 Correct 8 ms 20668 KB Output is correct
4 Correct 8 ms 20412 KB Output is correct
5 Correct 7 ms 20616 KB Output is correct
6 Correct 8 ms 20096 KB Output is correct
7 Correct 11 ms 20348 KB Output is correct
8 Correct 15 ms 20516 KB Output is correct
9 Correct 16 ms 20300 KB Output is correct
10 Correct 16 ms 20512 KB Output is correct
11 Correct 15 ms 20032 KB Output is correct
12 Correct 13 ms 20260 KB Output is correct
13 Correct 15 ms 19776 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 20412 KB Output is correct
2 Correct 8 ms 20760 KB Output is correct
3 Correct 8 ms 20668 KB Output is correct
4 Correct 8 ms 20412 KB Output is correct
5 Correct 7 ms 20616 KB Output is correct
6 Correct 8 ms 20096 KB Output is correct
7 Correct 11 ms 20348 KB Output is correct
8 Correct 15 ms 20516 KB Output is correct
9 Correct 16 ms 20300 KB Output is correct
10 Correct 16 ms 20512 KB Output is correct
11 Correct 15 ms 20032 KB Output is correct
12 Correct 13 ms 20260 KB Output is correct
13 Correct 15 ms 19776 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 20412 KB Output is correct
2 Correct 8 ms 20760 KB Output is correct
3 Correct 8 ms 20668 KB Output is correct
4 Correct 8 ms 20412 KB Output is correct
5 Correct 7 ms 20616 KB Output is correct
6 Correct 8 ms 20096 KB Output is correct
7 Correct 11 ms 20348 KB Output is correct
8 Correct 15 ms 20516 KB Output is correct
9 Correct 16 ms 20300 KB Output is correct
10 Correct 16 ms 20512 KB Output is correct
11 Correct 15 ms 20032 KB Output is correct
12 Correct 13 ms 20260 KB Output is correct
13 Correct 15 ms 19776 KB Output is correct
14 Incorrect 3 ms 2688 KB Incorrect
15 Halted 0 ms 0 KB -