oj.uz

Submission #981766

# Submission time Handle Problem Language Result Execution time Memory
981766 2024-05-13T14:27:47 Z bachhoangxuan Mars (APIO22_mars) C++17
29 / 100
 96 ms 4884 KB 
#include "mars.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 50;
#define pii pair<int,int>
#define fi first
#define se second

int dx[]={0,0,1,-1},
    dy[]={1,-1,0,0};

char c[maxn][maxn];
int f[maxn][maxn],cnt,K;

bool check(int x,int y){
    return (x<0 || y<0 || x>K || y>K || min(x,y)>2 || c[x][y]=='0');
}

void dfs(int x,int y){
    for(int t=0;t<4;t++){
        int xt=x+dx[t],yt=y+dy[t];
        if(check(xt,yt) || f[xt][yt]) continue;
        f[xt][yt]=f[x][y];
        dfs(xt,yt);
    }
}

int par[maxn];
bool used[maxn];
int findpar(int u){
    if(u!=par[u]) return par[u]=findpar(par[u]);
    return u;
}
void unions(int u,int v){
    u=findpar(u);v=findpar(v);
    if(u==v) return;
    par[v]=u;
}

string process(std::vector <std::vector<std::string>> a, int x, int y, int k, int n)
{

    if(max(x,y)<=2*(n-k-2)) return a[0][0];
    else if(x>y){
        a[0][0][1]=a[1][0][0];
        for(int i=0;i<=2*k;i++) a[0][0][2+i]=a[2][0][i];
        return a[0][0];
    }
    else if(x<y){
        a[0][0][1]=a[0][1][0];
        for(int i=0;i<=2*k;i++) a[0][0][2+i]=a[0][2][i];
        return a[0][0];
    }
    else if(x==2*(n-k-1)-1){
        for(int i=0;i<=2*k;i++) a[0][0][1+i]=a[1][2][i];
        for(int i=0;i<=2*k;i++) a[0][0][1+2*k+1+i]=a[2][1][i];
        return a[0][0];
    }
    else{
        for(int i=0;i<=2;i++) for(int j=0;j<=2;j++) c[i][j]=a[i][j][0];
        for(int i=1;i<=2*k;i++){
            c[0][2+i]=a[0][2][i];
            c[1][2+i]=a[1][2][i];
            c[2+i][0]=a[2][0][i];
            c[2+i][1]=a[2][1][i];
        }
        for(int i=0;i<=2*(k-1);i++){
            c[2][3+i]=a[1][1][1+i];
            c[3+i][2]=a[1][1][1+2*(k-1)+1+i];
        }
        if(k){
            c[2][2*k+2]=a[2][2][1];
            c[2*k+2][2]=a[2][2][2];
        }
        vector<vector<pii>> p;
        vector<pii> cur;

        for(int i=2*k+2;i>=2;i--){
            for(int j=2;j<=2*k+2 && min(i,j)<=2;j++){
                //if(k) cout << c[i][j];
                if(c[i][j]=='1') cur.push_back({i,j});
                else if(!cur.empty()){
                    p.push_back(cur);
                    cur.clear();
                }
            }
            //if(k) cout << '\n';
        }
        if(!cur.empty()) p.push_back(cur);

        memset(f,0,sizeof(f));
        int sz=(int)p.size();
        string S;cnt=0;
        vector<int> x(sz,0);

        if(k){
            for(int i=0;i<2*sz;i++) S+=a[2][2][3+i];
            //cout << "*" << k << ' ' << S << '\n';
            vector<int> cc;
            for(int i=0;i<sz;i++){
                if(S[i<<1]=='1'){
                    x[i]=++cnt;
                    cc.push_back(i);
                }
                if(S[i<<1|1]=='1'){
                    x[i]=x[cc.back()];
                    cc.pop_back();
                }
                if(S[i<<1]=='0' && S[i<<1|1]=='0') x[i]=x[cc.back()];
            }
            //cout << x[0] << ' ' << x[1] << '\n';
            for(int i=0;i<sz;i++) for(auto [u,v]:p[i]) f[u][v]=x[i];
        }

        K=2*k+2;
        for(int i=0;i<=2*k+2;i++){
            for(int j=0;j<=2*k+2 && min(i,j)<=2;j++){
                if(c[i][j]=='1'){
                    if(!f[i][j]) f[i][j]=++cnt;
                    dfs(i,j);
                }
                //if(k) cout << c[i][j];
            }
            //if(k) cout << '\n';
        }

        for(int i=1;i<=cnt;i++) par[i]=i,used[i]=false;
        for(int i=0;i<=2*k+2;i++) for(int j=0;j<=2*k+2 && min(i,j)<=2;j++){
            if(c[i][j]!='1') continue;
            for(int t=0;t<4;t++){
                int xt=i+dx[t],yt=j+dy[t];
                if(check(xt,yt)) continue;
                unions(f[i][j],f[xt][yt]);
            }
        }
        /*
        for(int i=0;i<=2*k+2;i++){
            for(int j=0;j<=2*k+2 && min(i,j)<=2;j++) cout << findpar(f[i][j]);
            cout << '\n';
        }
        */

        for(int i=0;i<=2*k+2;i++){
            for(int j=0;j<=2*k+2 && min(i,j)==0;j++){
                f[i][j]=findpar(f[i][j]);
                used[f[i][j]]=true;
                //cout << f[i][j];
            }
            //cout << '\n';
        }
        //cout << '*' << cnt << '\n';
        int num=0;
        if(k){
            for(int i=9;i>=0;i--) num=num<<1|(a[2][2][3+2*sz+i]-'0');
            //cout << '*' << num << '\n';
        }
        for(int i=1;i<=cnt;i++) if(findpar(i)==i && !used[i]) num++;

        if(k==n-1){
            for(int i=1;i<=cnt;i++) if(findpar(i)==i && used[i]) num++;
            string res;
            for(int i=0;i<10;i++) res+=char((num>>i&1)+'0');
            while((int)res.length()<100) res+='0';
            return res;
        }

        string res;
        res+=c[0][0];
        res+=c[0][2*k+2];
        res+=c[2*k+2][0];

        p.clear();
        cur.clear();
        for(int i=2*k+2;i>=0;i--) for(int j=0;j<=2*k+2 && min(i,j)==0;j++){
            if(c[i][j]=='1') cur.push_back({i,j});
            else if(!cur.empty()){
                p.push_back(cur);
                cur.clear();
            }
        }
        if(!cur.empty()) p.push_back(cur);

        sz=(int)p.size();
        x.assign(sz,0);
        for(int i=0;i<sz;i++) x[i]=f[p[i][0].fi][p[i][0].se];
        string add(2*sz,'0');

        vector<int> lst(cnt+1,-1);
        for(int i=0;i<sz;i++){
            if(lst[x[i]]==-1) add[i<<1]='1';
            lst[x[i]]=i;
        }
        for(int i=1;i<=cnt;i++) if(lst[i]!=-1) add[lst[i]<<1|1]='1';
        //cout << "***" << add << '\n';
        res+=add;
        for(int i=0;i<10;i++) res+=char((num>>i&1)+'0');
        while((int)res.length()<100) res+='0';
        return res;
    }
	return std::string(100 ,'0');
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4060 KB Output is correct
2 Correct 6 ms 3484 KB Output is correct
3 Correct 5 ms 4412 KB Output is correct
4 Correct 6 ms 3656 KB Output is correct
5 Correct 4 ms 3816 KB Output is correct
6 Correct 6 ms 3828 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4060 KB Output is correct
2 Correct 6 ms 3484 KB Output is correct
3 Correct 5 ms 4412 KB Output is correct
4 Correct 6 ms 3656 KB Output is correct
5 Correct 4 ms 3816 KB Output is correct
6 Correct 6 ms 3828 KB Output is correct
7 Correct 8 ms 4092 KB Output is correct
8 Correct 12 ms 3604 KB Output is correct
9 Correct 9 ms 3708 KB Output is correct
10 Correct 10 ms 4024 KB Output is correct
11 Correct 8 ms 4008 KB Output is correct
12 Correct 8 ms 4028 KB Output is correct
13 Correct 8 ms 3300 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4060 KB Output is correct
2 Correct 6 ms 3484 KB Output is correct
3 Correct 5 ms 4412 KB Output is correct
4 Correct 6 ms 3656 KB Output is correct
5 Correct 4 ms 3816 KB Output is correct
6 Correct 6 ms 3828 KB Output is correct
7 Correct 8 ms 4092 KB Output is correct
8 Correct 12 ms 3604 KB Output is correct
9 Correct 9 ms 3708 KB Output is correct
10 Correct 10 ms 4024 KB Output is correct
11 Correct 8 ms 4008 KB Output is correct
12 Correct 8 ms 4028 KB Output is correct
13 Correct 8 ms 3300 KB Output is correct
14 Correct 18 ms 4116 KB Output is correct
15 Correct 24 ms 3996 KB Output is correct
16 Correct 22 ms 4464 KB Output is correct
17 Correct 23 ms 4456 KB Output is correct
18 Correct 23 ms 4380 KB Output is correct
19 Correct 23 ms 4536 KB Output is correct
20 Correct 22 ms 4636 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4060 KB Output is correct
2 Correct 6 ms 3484 KB Output is correct
3 Correct 5 ms 4412 KB Output is correct
4 Correct 6 ms 3656 KB Output is correct
5 Correct 4 ms 3816 KB Output is correct
6 Correct 6 ms 3828 KB Output is correct
7 Correct 8 ms 4092 KB Output is correct
8 Correct 12 ms 3604 KB Output is correct
9 Correct 9 ms 3708 KB Output is correct
10 Correct 10 ms 4024 KB Output is correct
11 Correct 8 ms 4008 KB Output is correct
12 Correct 8 ms 4028 KB Output is correct
13 Correct 8 ms 3300 KB Output is correct
14 Correct 18 ms 4116 KB Output is correct
15 Correct 24 ms 3996 KB Output is correct
16 Correct 22 ms 4464 KB Output is correct
17 Correct 23 ms 4456 KB Output is correct
18 Correct 23 ms 4380 KB Output is correct
19 Correct 23 ms 4536 KB Output is correct
20 Correct 22 ms 4636 KB Output is correct
21 Correct 40 ms 4496 KB Output is correct
22 Correct 46 ms 4524 KB Output is correct
23 Correct 48 ms 4300 KB Output is correct
24 Correct 53 ms 4392 KB Output is correct
25 Correct 46 ms 4444 KB Output is correct
26 Correct 48 ms 4088 KB Output is correct
27 Correct 55 ms 4280 KB Output is correct
28 Correct 46 ms 3932 KB Output is correct

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4060 KB Output is correct
2 Correct 6 ms 3484 KB Output is correct
3 Correct 5 ms 4412 KB Output is correct
4 Correct 6 ms 3656 KB Output is correct
5 Correct 4 ms 3816 KB Output is correct
6 Correct 6 ms 3828 KB Output is correct
7 Correct 8 ms 4092 KB Output is correct
8 Correct 12 ms 3604 KB Output is correct
9 Correct 9 ms 3708 KB Output is correct
10 Correct 10 ms 4024 KB Output is correct
11 Correct 8 ms 4008 KB Output is correct
12 Correct 8 ms 4028 KB Output is correct
13 Correct 8 ms 3300 KB Output is correct
14 Correct 18 ms 4116 KB Output is correct
15 Correct 24 ms 3996 KB Output is correct
16 Correct 22 ms 4464 KB Output is correct
17 Correct 23 ms 4456 KB Output is correct
18 Correct 23 ms 4380 KB Output is correct
19 Correct 23 ms 4536 KB Output is correct
20 Correct 22 ms 4636 KB Output is correct
21 Correct 40 ms 4496 KB Output is correct
22 Correct 46 ms 4524 KB Output is correct
23 Correct 48 ms 4300 KB Output is correct
24 Correct 53 ms 4392 KB Output is correct
25 Correct 46 ms 4444 KB Output is correct
26 Correct 48 ms 4088 KB Output is correct
27 Correct 55 ms 4280 KB Output is correct
28 Correct 46 ms 3932 KB Output is correct
29 Correct 71 ms 4500 KB Output is correct
30 Correct 90 ms 4104 KB Output is correct
31 Correct 89 ms 4884 KB Output is correct
32 Correct 87 ms 4552 KB Output is correct
33 Correct 96 ms 4300 KB Output is correct
34 Correct 92 ms 4592 KB Output is correct
35 Correct 93 ms 4464 KB Output is correct
36 Incorrect 12 ms 492 KB Incorrect
37 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4060 KB Output is correct
2 Correct 6 ms 3484 KB Output is correct
3 Correct 5 ms 4412 KB Output is correct
4 Correct 6 ms 3656 KB Output is correct
5 Correct 4 ms 3816 KB Output is correct
6 Correct 6 ms 3828 KB Output is correct
7 Correct 8 ms 4092 KB Output is correct
8 Correct 12 ms 3604 KB Output is correct
9 Correct 9 ms 3708 KB Output is correct
10 Correct 10 ms 4024 KB Output is correct
11 Correct 8 ms 4008 KB Output is correct
12 Correct 8 ms 4028 KB Output is correct
13 Correct 8 ms 3300 KB Output is correct
14 Correct 18 ms 4116 KB Output is correct
15 Correct 24 ms 3996 KB Output is correct
16 Correct 22 ms 4464 KB Output is correct
17 Correct 23 ms 4456 KB Output is correct
18 Correct 23 ms 4380 KB Output is correct
19 Correct 23 ms 4536 KB Output is correct
20 Correct 22 ms 4636 KB Output is correct
21 Correct 40 ms 4496 KB Output is correct
22 Correct 46 ms 4524 KB Output is correct
23 Correct 48 ms 4300 KB Output is correct
24 Correct 53 ms 4392 KB Output is correct
25 Correct 46 ms 4444 KB Output is correct
26 Correct 48 ms 4088 KB Output is correct
27 Correct 55 ms 4280 KB Output is correct
28 Correct 46 ms 3932 KB Output is correct
29 Correct 71 ms 4500 KB Output is correct
30 Correct 90 ms 4104 KB Output is correct
31 Correct 89 ms 4884 KB Output is correct
32 Correct 87 ms 4552 KB Output is correct
33 Correct 96 ms 4300 KB Output is correct
34 Correct 92 ms 4592 KB Output is correct
35 Correct 93 ms 4464 KB Output is correct
36 Incorrect 12 ms 492 KB Incorrect
37 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4060 KB Output is correct
2 Correct 6 ms 3484 KB Output is correct
3 Correct 5 ms 4412 KB Output is correct
4 Correct 6 ms 3656 KB Output is correct
5 Correct 4 ms 3816 KB Output is correct
6 Correct 6 ms 3828 KB Output is correct
7 Correct 8 ms 4092 KB Output is correct
8 Correct 12 ms 3604 KB Output is correct
9 Correct 9 ms 3708 KB Output is correct
10 Correct 10 ms 4024 KB Output is correct
11 Correct 8 ms 4008 KB Output is correct
12 Correct 8 ms 4028 KB Output is correct
13 Correct 8 ms 3300 KB Output is correct
14 Correct 18 ms 4116 KB Output is correct
15 Correct 24 ms 3996 KB Output is correct
16 Correct 22 ms 4464 KB Output is correct
17 Correct 23 ms 4456 KB Output is correct
18 Correct 23 ms 4380 KB Output is correct
19 Correct 23 ms 4536 KB Output is correct
20 Correct 22 ms 4636 KB Output is correct
21 Correct 40 ms 4496 KB Output is correct
22 Correct 46 ms 4524 KB Output is correct
23 Correct 48 ms 4300 KB Output is correct
24 Correct 53 ms 4392 KB Output is correct
25 Correct 46 ms 4444 KB Output is correct
26 Correct 48 ms 4088 KB Output is correct
27 Correct 55 ms 4280 KB Output is correct
28 Correct 46 ms 3932 KB Output is correct
29 Correct 71 ms 4500 KB Output is correct
30 Correct 90 ms 4104 KB Output is correct
31 Correct 89 ms 4884 KB Output is correct
32 Correct 87 ms 4552 KB Output is correct
33 Correct 96 ms 4300 KB Output is correct
34 Correct 92 ms 4592 KB Output is correct
35 Correct 93 ms 4464 KB Output is correct
36 Incorrect 12 ms 492 KB Incorrect
37 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4060 KB Output is correct
2 Correct 6 ms 3484 KB Output is correct
3 Correct 5 ms 4412 KB Output is correct
4 Correct 6 ms 3656 KB Output is correct
5 Correct 4 ms 3816 KB Output is correct
6 Correct 6 ms 3828 KB Output is correct
7 Correct 8 ms 4092 KB Output is correct
8 Correct 12 ms 3604 KB Output is correct
9 Correct 9 ms 3708 KB Output is correct
10 Correct 10 ms 4024 KB Output is correct
11 Correct 8 ms 4008 KB Output is correct
12 Correct 8 ms 4028 KB Output is correct
13 Correct 8 ms 3300 KB Output is correct
14 Correct 18 ms 4116 KB Output is correct
15 Correct 24 ms 3996 KB Output is correct
16 Correct 22 ms 4464 KB Output is correct
17 Correct 23 ms 4456 KB Output is correct
18 Correct 23 ms 4380 KB Output is correct
19 Correct 23 ms 4536 KB Output is correct
20 Correct 22 ms 4636 KB Output is correct
21 Correct 40 ms 4496 KB Output is correct
22 Correct 46 ms 4524 KB Output is correct
23 Correct 48 ms 4300 KB Output is correct
24 Correct 53 ms 4392 KB Output is correct
25 Correct 46 ms 4444 KB Output is correct
26 Correct 48 ms 4088 KB Output is correct
27 Correct 55 ms 4280 KB Output is correct
28 Correct 46 ms 3932 KB Output is correct
29 Correct 71 ms 4500 KB Output is correct
30 Correct 90 ms 4104 KB Output is correct
31 Correct 89 ms 4884 KB Output is correct
32 Correct 87 ms 4552 KB Output is correct
33 Correct 96 ms 4300 KB Output is correct
34 Correct 92 ms 4592 KB Output is correct
35 Correct 93 ms 4464 KB Output is correct
36 Incorrect 12 ms 492 KB Incorrect
37 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4060 KB Output is correct
2 Correct 6 ms 3484 KB Output is correct
3 Correct 5 ms 4412 KB Output is correct
4 Correct 6 ms 3656 KB Output is correct
5 Correct 4 ms 3816 KB Output is correct
6 Correct 6 ms 3828 KB Output is correct
7 Correct 8 ms 4092 KB Output is correct
8 Correct 12 ms 3604 KB Output is correct
9 Correct 9 ms 3708 KB Output is correct
10 Correct 10 ms 4024 KB Output is correct
11 Correct 8 ms 4008 KB Output is correct
12 Correct 8 ms 4028 KB Output is correct
13 Correct 8 ms 3300 KB Output is correct
14 Correct 18 ms 4116 KB Output is correct
15 Correct 24 ms 3996 KB Output is correct
16 Correct 22 ms 4464 KB Output is correct
17 Correct 23 ms 4456 KB Output is correct
18 Correct 23 ms 4380 KB Output is correct
19 Correct 23 ms 4536 KB Output is correct
20 Correct 22 ms 4636 KB Output is correct
21 Correct 40 ms 4496 KB Output is correct
22 Correct 46 ms 4524 KB Output is correct
23 Correct 48 ms 4300 KB Output is correct
24 Correct 53 ms 4392 KB Output is correct
25 Correct 46 ms 4444 KB Output is correct
26 Correct 48 ms 4088 KB Output is correct
27 Correct 55 ms 4280 KB Output is correct
28 Correct 46 ms 3932 KB Output is correct
29 Correct 71 ms 4500 KB Output is correct
30 Correct 90 ms 4104 KB Output is correct
31 Correct 89 ms 4884 KB Output is correct
32 Correct 87 ms 4552 KB Output is correct
33 Correct 96 ms 4300 KB Output is correct
34 Correct 92 ms 4592 KB Output is correct
35 Correct 93 ms 4464 KB Output is correct
36 Incorrect 12 ms 492 KB Incorrect
37 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4060 KB Output is correct
2 Correct 6 ms 3484 KB Output is correct
3 Correct 5 ms 4412 KB Output is correct
4 Correct 6 ms 3656 KB Output is correct
5 Correct 4 ms 3816 KB Output is correct
6 Correct 6 ms 3828 KB Output is correct
7 Correct 8 ms 4092 KB Output is correct
8 Correct 12 ms 3604 KB Output is correct
9 Correct 9 ms 3708 KB Output is correct
10 Correct 10 ms 4024 KB Output is correct
11 Correct 8 ms 4008 KB Output is correct
12 Correct 8 ms 4028 KB Output is correct
13 Correct 8 ms 3300 KB Output is correct
14 Correct 18 ms 4116 KB Output is correct
15 Correct 24 ms 3996 KB Output is correct
16 Correct 22 ms 4464 KB Output is correct
17 Correct 23 ms 4456 KB Output is correct
18 Correct 23 ms 4380 KB Output is correct
19 Correct 23 ms 4536 KB Output is correct
20 Correct 22 ms 4636 KB Output is correct
21 Correct 40 ms 4496 KB Output is correct
22 Correct 46 ms 4524 KB Output is correct
23 Correct 48 ms 4300 KB Output is correct
24 Correct 53 ms 4392 KB Output is correct
25 Correct 46 ms 4444 KB Output is correct
26 Correct 48 ms 4088 KB Output is correct
27 Correct 55 ms 4280 KB Output is correct
28 Correct 46 ms 3932 KB Output is correct
29 Correct 71 ms 4500 KB Output is correct
30 Correct 90 ms 4104 KB Output is correct
31 Correct 89 ms 4884 KB Output is correct
32 Correct 87 ms 4552 KB Output is correct
33 Correct 96 ms 4300 KB Output is correct
34 Correct 92 ms 4592 KB Output is correct
35 Correct 93 ms 4464 KB Output is correct
36 Incorrect 12 ms 492 KB Incorrect
37 Halted 0 ms 0 KB -