oj.uz

Submission #957689

# Submission time Handle Problem Language Result Execution time Memory
957689 2024-04-04T08:13:23 Z vjudge1 Mars (APIO22_mars) C++17
14 / 100
 35 ms 25540 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;
             }
        }
    }
    for(int k=0;k<=4;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]=i, ly[i][j][k]=j;
                rx[i][j][k]=i+2*k, ry[i][j][k]=j+2*k;
            }
        }
    }
    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<i+2*k+1;x1++){
                            for(int y1=j;y1<j+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, 2*n), ry[x][y][k-1]=min(fy+9, 2*n);
                        }
                        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 9 ms 25208 KB Output is correct
2 Correct 8 ms 24892 KB Output is correct
3 Correct 12 ms 25068 KB Output is correct
4 Correct 10 ms 25540 KB Output is correct
5 Correct 8 ms 24724 KB Output is correct
6 Correct 8 ms 24888 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25208 KB Output is correct
2 Correct 8 ms 24892 KB Output is correct
3 Correct 12 ms 25068 KB Output is correct
4 Correct 10 ms 25540 KB Output is correct
5 Correct 8 ms 24724 KB Output is correct
6 Correct 8 ms 24888 KB Output is correct
7 Correct 16 ms 25176 KB Output is correct
8 Correct 25 ms 25500 KB Output is correct
9 Correct 26 ms 25064 KB Output is correct
10 Correct 29 ms 25012 KB Output is correct
11 Correct 27 ms 25188 KB Output is correct
12 Correct 35 ms 25384 KB Output is correct
13 Correct 34 ms 25024 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25208 KB Output is correct
2 Correct 8 ms 24892 KB Output is correct
3 Correct 12 ms 25068 KB Output is correct
4 Correct 10 ms 25540 KB Output is correct
5 Correct 8 ms 24724 KB Output is correct
6 Correct 8 ms 24888 KB Output is correct
7 Correct 16 ms 25176 KB Output is correct
8 Correct 25 ms 25500 KB Output is correct
9 Correct 26 ms 25064 KB Output is correct
10 Correct 29 ms 25012 KB Output is correct
11 Correct 27 ms 25188 KB Output is correct
12 Correct 35 ms 25384 KB Output is correct
13 Correct 34 ms 25024 KB Output is correct
14 Incorrect 12 ms 2676 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25208 KB Output is correct
2 Correct 8 ms 24892 KB Output is correct
3 Correct 12 ms 25068 KB Output is correct
4 Correct 10 ms 25540 KB Output is correct
5 Correct 8 ms 24724 KB Output is correct
6 Correct 8 ms 24888 KB Output is correct
7 Correct 16 ms 25176 KB Output is correct
8 Correct 25 ms 25500 KB Output is correct
9 Correct 26 ms 25064 KB Output is correct
10 Correct 29 ms 25012 KB Output is correct
11 Correct 27 ms 25188 KB Output is correct
12 Correct 35 ms 25384 KB Output is correct
13 Correct 34 ms 25024 KB Output is correct
14 Incorrect 12 ms 2676 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25208 KB Output is correct
2 Correct 8 ms 24892 KB Output is correct
3 Correct 12 ms 25068 KB Output is correct
4 Correct 10 ms 25540 KB Output is correct
5 Correct 8 ms 24724 KB Output is correct
6 Correct 8 ms 24888 KB Output is correct
7 Correct 16 ms 25176 KB Output is correct
8 Correct 25 ms 25500 KB Output is correct
9 Correct 26 ms 25064 KB Output is correct
10 Correct 29 ms 25012 KB Output is correct
11 Correct 27 ms 25188 KB Output is correct
12 Correct 35 ms 25384 KB Output is correct
13 Correct 34 ms 25024 KB Output is correct
14 Incorrect 12 ms 2676 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25208 KB Output is correct
2 Correct 8 ms 24892 KB Output is correct
3 Correct 12 ms 25068 KB Output is correct
4 Correct 10 ms 25540 KB Output is correct
5 Correct 8 ms 24724 KB Output is correct
6 Correct 8 ms 24888 KB Output is correct
7 Correct 16 ms 25176 KB Output is correct
8 Correct 25 ms 25500 KB Output is correct
9 Correct 26 ms 25064 KB Output is correct
10 Correct 29 ms 25012 KB Output is correct
11 Correct 27 ms 25188 KB Output is correct
12 Correct 35 ms 25384 KB Output is correct
13 Correct 34 ms 25024 KB Output is correct
14 Incorrect 12 ms 2676 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25208 KB Output is correct
2 Correct 8 ms 24892 KB Output is correct
3 Correct 12 ms 25068 KB Output is correct
4 Correct 10 ms 25540 KB Output is correct
5 Correct 8 ms 24724 KB Output is correct
6 Correct 8 ms 24888 KB Output is correct
7 Correct 16 ms 25176 KB Output is correct
8 Correct 25 ms 25500 KB Output is correct
9 Correct 26 ms 25064 KB Output is correct
10 Correct 29 ms 25012 KB Output is correct
11 Correct 27 ms 25188 KB Output is correct
12 Correct 35 ms 25384 KB Output is correct
13 Correct 34 ms 25024 KB Output is correct
14 Incorrect 12 ms 2676 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25208 KB Output is correct
2 Correct 8 ms 24892 KB Output is correct
3 Correct 12 ms 25068 KB Output is correct
4 Correct 10 ms 25540 KB Output is correct
5 Correct 8 ms 24724 KB Output is correct
6 Correct 8 ms 24888 KB Output is correct
7 Correct 16 ms 25176 KB Output is correct
8 Correct 25 ms 25500 KB Output is correct
9 Correct 26 ms 25064 KB Output is correct
10 Correct 29 ms 25012 KB Output is correct
11 Correct 27 ms 25188 KB Output is correct
12 Correct 35 ms 25384 KB Output is correct
13 Correct 34 ms 25024 KB Output is correct
14 Incorrect 12 ms 2676 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25208 KB Output is correct
2 Correct 8 ms 24892 KB Output is correct
3 Correct 12 ms 25068 KB Output is correct
4 Correct 10 ms 25540 KB Output is correct
5 Correct 8 ms 24724 KB Output is correct
6 Correct 8 ms 24888 KB Output is correct
7 Correct 16 ms 25176 KB Output is correct
8 Correct 25 ms 25500 KB Output is correct
9 Correct 26 ms 25064 KB Output is correct
10 Correct 29 ms 25012 KB Output is correct
11 Correct 27 ms 25188 KB Output is correct
12 Correct 35 ms 25384 KB Output is correct
13 Correct 34 ms 25024 KB Output is correct
14 Incorrect 12 ms 2676 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25208 KB Output is correct
2 Correct 8 ms 24892 KB Output is correct
3 Correct 12 ms 25068 KB Output is correct
4 Correct 10 ms 25540 KB Output is correct
5 Correct 8 ms 24724 KB Output is correct
6 Correct 8 ms 24888 KB Output is correct
7 Correct 16 ms 25176 KB Output is correct
8 Correct 25 ms 25500 KB Output is correct
9 Correct 26 ms 25064 KB Output is correct
10 Correct 29 ms 25012 KB Output is correct
11 Correct 27 ms 25188 KB Output is correct
12 Correct 35 ms 25384 KB Output is correct
13 Correct 34 ms 25024 KB Output is correct
14 Incorrect 12 ms 2676 KB Incorrect
15 Halted 0 ms 0 KB -