oj.uz

Submission #957661

# Submission time Handle Problem Language Result Execution time Memory
957661 2024-04-04T07:22:49 Z vjudge1 Mars (APIO22_mars) C++17
21 / 100
 28 ms 4552 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=1e6+12;
const int mod=998244353;
const bool T=1;

int used[200][200];

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);
        }
    }
}

std::string process(std::vector<std::vector<std::string> > a,int x,int y,int k,int n){
    k++;
    if(k==5){
        string ans="";
        while(ans.size()<100){
            ans+='0';
        }
        for(int i=x;i<x+2*k+1;i++){
            for(int j=y;j<y+2*k+1;j++){
                int lx=min(i, x+2), rx=min(j, y+2);
                used[i][j]=(a[lx-x][rx-y][pos(i-lx, j-rx, 2*k-1)] == '1');
            }
        }
        if(k==n){
            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;
        }
        int lx = x, ly = y, rx = x + 9, ry = y+9;
        if(x==2){
            lx++, rx++;
        }
        if(y==2){
            ly++, ry++;
        }
        int pos=0;
        for(int i=lx;i<=rx;i++){
            for(int j=ly;j<=ry;j++){
                ans[pos]=used[i][j] + '0';
                pos++;
            }
        }
        return ans;
    }
    string ans="";
    while(ans.size()<100){
        ans+='0';
    }
    if(k<5){
        for(int i=x;i<x+2*k+1;i++){
            for(int j=y;j<y+2*k+1;j++){
                int lx=min(i, x+2), rx=min(j, y+2);
                ans[pos(i-x, j-y, 2*k+1)]=a[lx-x][rx-y][pos(i-lx, j-rx, 2*k-1)];
            }
        }
    }
    if(k==n){
        if(k==6){
            int pos=0;
            for(int i=0;i<10;i++){
                for(int j=0;j<10;j++){
                    used[i][j]=(a[0][0][pos] == '0');
                    pos++;
                }
            }
            pos=0;
            for(int i=3;i<13;i++){
                for(int j=0;j<10;j++){
                    used[i][j]=(a[2][0][pos] == '0');
                    pos++;
                }
            }
            pos=0;
            for(int i=3;i<13;i++){
                for(int j=3;j<13;j++){
                    used[i][j]=(a[2][2][pos] == '0');
                    pos++;
                }
            }
            pos=0;
            for(int i=0;i<10;i++){
                for(int j=3;j<13;j++){
                    used[i][j]=(a[0][2][pos] == '0');
                    pos++;
                }
            }
        }
        else{
            for(int i=0;i<2*n+1;i++){
                for(int j=0;j<2*n+1;j++){
                    used[i][j]=(ans[pos(i, j, 2*n+1)] == '0');
                }
            }
        }
        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;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4012 KB Output is correct
2 Correct 1 ms 3844 KB Output is correct
3 Correct 8 ms 4152 KB Output is correct
4 Correct 4 ms 3984 KB Output is correct
5 Correct 6 ms 4552 KB Output is correct
6 Correct 8 ms 4492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4012 KB Output is correct
2 Correct 1 ms 3844 KB Output is correct
3 Correct 8 ms 4152 KB Output is correct
4 Correct 4 ms 3984 KB Output is correct
5 Correct 6 ms 4552 KB Output is correct
6 Correct 8 ms 4492 KB Output is correct
7 Correct 8 ms 4004 KB Output is correct
8 Correct 9 ms 4048 KB Output is correct
9 Correct 11 ms 3896 KB Output is correct
10 Correct 8 ms 4352 KB Output is correct
11 Correct 10 ms 3784 KB Output is correct
12 Correct 11 ms 4352 KB Output is correct
13 Correct 9 ms 4232 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4012 KB Output is correct
2 Correct 1 ms 3844 KB Output is correct
3 Correct 8 ms 4152 KB Output is correct
4 Correct 4 ms 3984 KB Output is correct
5 Correct 6 ms 4552 KB Output is correct
6 Correct 8 ms 4492 KB Output is correct
7 Correct 8 ms 4004 KB Output is correct
8 Correct 9 ms 4048 KB Output is correct
9 Correct 11 ms 3896 KB Output is correct
10 Correct 8 ms 4352 KB Output is correct
11 Correct 10 ms 3784 KB Output is correct
12 Correct 11 ms 4352 KB Output is correct
13 Correct 9 ms 4232 KB Output is correct
14 Correct 18 ms 4168 KB Output is correct
15 Correct 27 ms 4356 KB Output is correct
16 Correct 23 ms 3920 KB Output is correct
17 Correct 24 ms 4388 KB Output is correct
18 Correct 28 ms 4444 KB Output is correct
19 Correct 23 ms 4456 KB Output is correct
20 Correct 24 ms 4228 KB Output is correct

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4012 KB Output is correct
2 Correct 1 ms 3844 KB Output is correct
3 Correct 8 ms 4152 KB Output is correct
4 Correct 4 ms 3984 KB Output is correct
5 Correct 6 ms 4552 KB Output is correct
6 Correct 8 ms 4492 KB Output is correct
7 Correct 8 ms 4004 KB Output is correct
8 Correct 9 ms 4048 KB Output is correct
9 Correct 11 ms 3896 KB Output is correct
10 Correct 8 ms 4352 KB Output is correct
11 Correct 10 ms 3784 KB Output is correct
12 Correct 11 ms 4352 KB Output is correct
13 Correct 9 ms 4232 KB Output is correct
14 Correct 18 ms 4168 KB Output is correct
15 Correct 27 ms 4356 KB Output is correct
16 Correct 23 ms 3920 KB Output is correct
17 Correct 24 ms 4388 KB Output is correct
18 Correct 28 ms 4444 KB Output is correct
19 Correct 23 ms 4456 KB Output is correct
20 Correct 24 ms 4228 KB Output is correct
21 Incorrect 5 ms 480 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4012 KB Output is correct
2 Correct 1 ms 3844 KB Output is correct
3 Correct 8 ms 4152 KB Output is correct
4 Correct 4 ms 3984 KB Output is correct
5 Correct 6 ms 4552 KB Output is correct
6 Correct 8 ms 4492 KB Output is correct
7 Correct 8 ms 4004 KB Output is correct
8 Correct 9 ms 4048 KB Output is correct
9 Correct 11 ms 3896 KB Output is correct
10 Correct 8 ms 4352 KB Output is correct
11 Correct 10 ms 3784 KB Output is correct
12 Correct 11 ms 4352 KB Output is correct
13 Correct 9 ms 4232 KB Output is correct
14 Correct 18 ms 4168 KB Output is correct
15 Correct 27 ms 4356 KB Output is correct
16 Correct 23 ms 3920 KB Output is correct
17 Correct 24 ms 4388 KB Output is correct
18 Correct 28 ms 4444 KB Output is correct
19 Correct 23 ms 4456 KB Output is correct
20 Correct 24 ms 4228 KB Output is correct
21 Incorrect 5 ms 480 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4012 KB Output is correct
2 Correct 1 ms 3844 KB Output is correct
3 Correct 8 ms 4152 KB Output is correct
4 Correct 4 ms 3984 KB Output is correct
5 Correct 6 ms 4552 KB Output is correct
6 Correct 8 ms 4492 KB Output is correct
7 Correct 8 ms 4004 KB Output is correct
8 Correct 9 ms 4048 KB Output is correct
9 Correct 11 ms 3896 KB Output is correct
10 Correct 8 ms 4352 KB Output is correct
11 Correct 10 ms 3784 KB Output is correct
12 Correct 11 ms 4352 KB Output is correct
13 Correct 9 ms 4232 KB Output is correct
14 Correct 18 ms 4168 KB Output is correct
15 Correct 27 ms 4356 KB Output is correct
16 Correct 23 ms 3920 KB Output is correct
17 Correct 24 ms 4388 KB Output is correct
18 Correct 28 ms 4444 KB Output is correct
19 Correct 23 ms 4456 KB Output is correct
20 Correct 24 ms 4228 KB Output is correct
21 Incorrect 5 ms 480 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4012 KB Output is correct
2 Correct 1 ms 3844 KB Output is correct
3 Correct 8 ms 4152 KB Output is correct
4 Correct 4 ms 3984 KB Output is correct
5 Correct 6 ms 4552 KB Output is correct
6 Correct 8 ms 4492 KB Output is correct
7 Correct 8 ms 4004 KB Output is correct
8 Correct 9 ms 4048 KB Output is correct
9 Correct 11 ms 3896 KB Output is correct
10 Correct 8 ms 4352 KB Output is correct
11 Correct 10 ms 3784 KB Output is correct
12 Correct 11 ms 4352 KB Output is correct
13 Correct 9 ms 4232 KB Output is correct
14 Correct 18 ms 4168 KB Output is correct
15 Correct 27 ms 4356 KB Output is correct
16 Correct 23 ms 3920 KB Output is correct
17 Correct 24 ms 4388 KB Output is correct
18 Correct 28 ms 4444 KB Output is correct
19 Correct 23 ms 4456 KB Output is correct
20 Correct 24 ms 4228 KB Output is correct
21 Incorrect 5 ms 480 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4012 KB Output is correct
2 Correct 1 ms 3844 KB Output is correct
3 Correct 8 ms 4152 KB Output is correct
4 Correct 4 ms 3984 KB Output is correct
5 Correct 6 ms 4552 KB Output is correct
6 Correct 8 ms 4492 KB Output is correct
7 Correct 8 ms 4004 KB Output is correct
8 Correct 9 ms 4048 KB Output is correct
9 Correct 11 ms 3896 KB Output is correct
10 Correct 8 ms 4352 KB Output is correct
11 Correct 10 ms 3784 KB Output is correct
12 Correct 11 ms 4352 KB Output is correct
13 Correct 9 ms 4232 KB Output is correct
14 Correct 18 ms 4168 KB Output is correct
15 Correct 27 ms 4356 KB Output is correct
16 Correct 23 ms 3920 KB Output is correct
17 Correct 24 ms 4388 KB Output is correct
18 Correct 28 ms 4444 KB Output is correct
19 Correct 23 ms 4456 KB Output is correct
20 Correct 24 ms 4228 KB Output is correct
21 Incorrect 5 ms 480 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4012 KB Output is correct
2 Correct 1 ms 3844 KB Output is correct
3 Correct 8 ms 4152 KB Output is correct
4 Correct 4 ms 3984 KB Output is correct
5 Correct 6 ms 4552 KB Output is correct
6 Correct 8 ms 4492 KB Output is correct
7 Correct 8 ms 4004 KB Output is correct
8 Correct 9 ms 4048 KB Output is correct
9 Correct 11 ms 3896 KB Output is correct
10 Correct 8 ms 4352 KB Output is correct
11 Correct 10 ms 3784 KB Output is correct
12 Correct 11 ms 4352 KB Output is correct
13 Correct 9 ms 4232 KB Output is correct
14 Correct 18 ms 4168 KB Output is correct
15 Correct 27 ms 4356 KB Output is correct
16 Correct 23 ms 3920 KB Output is correct
17 Correct 24 ms 4388 KB Output is correct
18 Correct 28 ms 4444 KB Output is correct
19 Correct 23 ms 4456 KB Output is correct
20 Correct 24 ms 4228 KB Output is correct
21 Incorrect 5 ms 480 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4012 KB Output is correct
2 Correct 1 ms 3844 KB Output is correct
3 Correct 8 ms 4152 KB Output is correct
4 Correct 4 ms 3984 KB Output is correct
5 Correct 6 ms 4552 KB Output is correct
6 Correct 8 ms 4492 KB Output is correct
7 Correct 8 ms 4004 KB Output is correct
8 Correct 9 ms 4048 KB Output is correct
9 Correct 11 ms 3896 KB Output is correct
10 Correct 8 ms 4352 KB Output is correct
11 Correct 10 ms 3784 KB Output is correct
12 Correct 11 ms 4352 KB Output is correct
13 Correct 9 ms 4232 KB Output is correct
14 Correct 18 ms 4168 KB Output is correct
15 Correct 27 ms 4356 KB Output is correct
16 Correct 23 ms 3920 KB Output is correct
17 Correct 24 ms 4388 KB Output is correct
18 Correct 28 ms 4444 KB Output is correct
19 Correct 23 ms 4456 KB Output is correct
20 Correct 24 ms 4228 KB Output is correct
21 Incorrect 5 ms 480 KB Incorrect
22 Halted 0 ms 0 KB -