oj.uz

답안 #957713

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957713 2024-04-04T08:38:17 Z vjudge1 화성 (APIO22_mars) C++17
21 / 100
 195 ms 21856 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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20088 KB Output is correct
3 Correct 8 ms 20360 KB Output is correct
4 Correct 8 ms 19932 KB Output is correct
5 Correct 8 ms 20512 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20088 KB Output is correct
3 Correct 8 ms 20360 KB Output is correct
4 Correct 8 ms 19932 KB Output is correct
5 Correct 8 ms 20512 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 13 ms 20144 KB Output is correct
8 Correct 24 ms 20552 KB Output is correct
9 Correct 23 ms 20216 KB Output is correct
10 Correct 23 ms 20396 KB Output is correct
11 Correct 22 ms 20088 KB Output is correct
12 Correct 23 ms 19956 KB Output is correct
13 Correct 23 ms 20512 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20088 KB Output is correct
3 Correct 8 ms 20360 KB Output is correct
4 Correct 8 ms 19932 KB Output is correct
5 Correct 8 ms 20512 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 13 ms 20144 KB Output is correct
8 Correct 24 ms 20552 KB Output is correct
9 Correct 23 ms 20216 KB Output is correct
10 Correct 23 ms 20396 KB Output is correct
11 Correct 22 ms 20088 KB Output is correct
12 Correct 23 ms 19956 KB Output is correct
13 Correct 23 ms 20512 KB Output is correct
14 Correct 88 ms 21552 KB Output is correct
15 Correct 173 ms 21460 KB Output is correct
16 Correct 188 ms 21472 KB Output is correct
17 Correct 180 ms 21560 KB Output is correct
18 Correct 183 ms 21856 KB Output is correct
19 Correct 176 ms 21576 KB Output is correct
20 Correct 195 ms 21616 KB Output is correct

Subtask #4
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20088 KB Output is correct
3 Correct 8 ms 20360 KB Output is correct
4 Correct 8 ms 19932 KB Output is correct
5 Correct 8 ms 20512 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 13 ms 20144 KB Output is correct
8 Correct 24 ms 20552 KB Output is correct
9 Correct 23 ms 20216 KB Output is correct
10 Correct 23 ms 20396 KB Output is correct
11 Correct 22 ms 20088 KB Output is correct
12 Correct 23 ms 19956 KB Output is correct
13 Correct 23 ms 20512 KB Output is correct
14 Correct 88 ms 21552 KB Output is correct
15 Correct 173 ms 21460 KB Output is correct
16 Correct 188 ms 21472 KB Output is correct
17 Correct 180 ms 21560 KB Output is correct
18 Correct 183 ms 21856 KB Output is correct
19 Correct 176 ms 21576 KB Output is correct
20 Correct 195 ms 21616 KB Output is correct
21 Incorrect 52 ms 2712 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20088 KB Output is correct
3 Correct 8 ms 20360 KB Output is correct
4 Correct 8 ms 19932 KB Output is correct
5 Correct 8 ms 20512 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 13 ms 20144 KB Output is correct
8 Correct 24 ms 20552 KB Output is correct
9 Correct 23 ms 20216 KB Output is correct
10 Correct 23 ms 20396 KB Output is correct
11 Correct 22 ms 20088 KB Output is correct
12 Correct 23 ms 19956 KB Output is correct
13 Correct 23 ms 20512 KB Output is correct
14 Correct 88 ms 21552 KB Output is correct
15 Correct 173 ms 21460 KB Output is correct
16 Correct 188 ms 21472 KB Output is correct
17 Correct 180 ms 21560 KB Output is correct
18 Correct 183 ms 21856 KB Output is correct
19 Correct 176 ms 21576 KB Output is correct
20 Correct 195 ms 21616 KB Output is correct
21 Incorrect 52 ms 2712 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20088 KB Output is correct
3 Correct 8 ms 20360 KB Output is correct
4 Correct 8 ms 19932 KB Output is correct
5 Correct 8 ms 20512 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 13 ms 20144 KB Output is correct
8 Correct 24 ms 20552 KB Output is correct
9 Correct 23 ms 20216 KB Output is correct
10 Correct 23 ms 20396 KB Output is correct
11 Correct 22 ms 20088 KB Output is correct
12 Correct 23 ms 19956 KB Output is correct
13 Correct 23 ms 20512 KB Output is correct
14 Correct 88 ms 21552 KB Output is correct
15 Correct 173 ms 21460 KB Output is correct
16 Correct 188 ms 21472 KB Output is correct
17 Correct 180 ms 21560 KB Output is correct
18 Correct 183 ms 21856 KB Output is correct
19 Correct 176 ms 21576 KB Output is correct
20 Correct 195 ms 21616 KB Output is correct
21 Incorrect 52 ms 2712 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20088 KB Output is correct
3 Correct 8 ms 20360 KB Output is correct
4 Correct 8 ms 19932 KB Output is correct
5 Correct 8 ms 20512 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 13 ms 20144 KB Output is correct
8 Correct 24 ms 20552 KB Output is correct
9 Correct 23 ms 20216 KB Output is correct
10 Correct 23 ms 20396 KB Output is correct
11 Correct 22 ms 20088 KB Output is correct
12 Correct 23 ms 19956 KB Output is correct
13 Correct 23 ms 20512 KB Output is correct
14 Correct 88 ms 21552 KB Output is correct
15 Correct 173 ms 21460 KB Output is correct
16 Correct 188 ms 21472 KB Output is correct
17 Correct 180 ms 21560 KB Output is correct
18 Correct 183 ms 21856 KB Output is correct
19 Correct 176 ms 21576 KB Output is correct
20 Correct 195 ms 21616 KB Output is correct
21 Incorrect 52 ms 2712 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20088 KB Output is correct
3 Correct 8 ms 20360 KB Output is correct
4 Correct 8 ms 19932 KB Output is correct
5 Correct 8 ms 20512 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 13 ms 20144 KB Output is correct
8 Correct 24 ms 20552 KB Output is correct
9 Correct 23 ms 20216 KB Output is correct
10 Correct 23 ms 20396 KB Output is correct
11 Correct 22 ms 20088 KB Output is correct
12 Correct 23 ms 19956 KB Output is correct
13 Correct 23 ms 20512 KB Output is correct
14 Correct 88 ms 21552 KB Output is correct
15 Correct 173 ms 21460 KB Output is correct
16 Correct 188 ms 21472 KB Output is correct
17 Correct 180 ms 21560 KB Output is correct
18 Correct 183 ms 21856 KB Output is correct
19 Correct 176 ms 21576 KB Output is correct
20 Correct 195 ms 21616 KB Output is correct
21 Incorrect 52 ms 2712 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20088 KB Output is correct
3 Correct 8 ms 20360 KB Output is correct
4 Correct 8 ms 19932 KB Output is correct
5 Correct 8 ms 20512 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 13 ms 20144 KB Output is correct
8 Correct 24 ms 20552 KB Output is correct
9 Correct 23 ms 20216 KB Output is correct
10 Correct 23 ms 20396 KB Output is correct
11 Correct 22 ms 20088 KB Output is correct
12 Correct 23 ms 19956 KB Output is correct
13 Correct 23 ms 20512 KB Output is correct
14 Correct 88 ms 21552 KB Output is correct
15 Correct 173 ms 21460 KB Output is correct
16 Correct 188 ms 21472 KB Output is correct
17 Correct 180 ms 21560 KB Output is correct
18 Correct 183 ms 21856 KB Output is correct
19 Correct 176 ms 21576 KB Output is correct
20 Correct 195 ms 21616 KB Output is correct
21 Incorrect 52 ms 2712 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20352 KB Output is correct
2 Correct 8 ms 20088 KB Output is correct
3 Correct 8 ms 20360 KB Output is correct
4 Correct 8 ms 19932 KB Output is correct
5 Correct 8 ms 20512 KB Output is correct
6 Correct 8 ms 20352 KB Output is correct
7 Correct 13 ms 20144 KB Output is correct
8 Correct 24 ms 20552 KB Output is correct
9 Correct 23 ms 20216 KB Output is correct
10 Correct 23 ms 20396 KB Output is correct
11 Correct 22 ms 20088 KB Output is correct
12 Correct 23 ms 19956 KB Output is correct
13 Correct 23 ms 20512 KB Output is correct
14 Correct 88 ms 21552 KB Output is correct
15 Correct 173 ms 21460 KB Output is correct
16 Correct 188 ms 21472 KB Output is correct
17 Correct 180 ms 21560 KB Output is correct
18 Correct 183 ms 21856 KB Output is correct
19 Correct 176 ms 21576 KB Output is correct
20 Correct 195 ms 21616 KB Output is correct
21 Incorrect 52 ms 2712 KB Incorrect
22 Halted 0 ms 0 KB -