oj.uz

Submission #821318

# Submission time Handle Problem Language Result Execution time Memory
821318 2023-08-11T09:06:13 Z Hanksburger Mars (APIO22_mars) C++17
14 / 100
 11 ms 2216 KB 
#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
string process(vector<vector<string> > a, int i, int j, int k, int n)
{
    int il0=(2*n+1)*  i  /(2*(n-k)+1)+1;
    int ir0=(2*n+1)*(i+1)/(2*(n-k)+1);
    int il1=(2*n+1)*(i+1)/(2*(n-k)+1)+1;
    int ir1=(2*n+1)*(i+2)/(2*(n-k)+1);
    int il2=(2*n+1)*(i+2)/(2*(n-k)+1)+1;
    int ir2=(2*n+1)*(i+3)/(2*(n-k)+1);
    
    int jl0=(2*n+1)*  j  /(2*(n-k)+1)+1;
    int jr0=(2*n+1)*(j+1)/(2*(n-k)+1);
    int jl1=(2*n+1)*(j+1)/(2*(n-k)+1)+1;
    int jr1=(2*n+1)*(j+2)/(2*(n-k)+1);
    int jl2=(2*n+1)*(j+2)/(2*(n-k)+1)+1;
    int jr2=(2*n+1)*(j+3)/(2*(n-k)+1);
    
    int iltarget=(2*n+1)*  i  /(2*(n-k-1)+1)+1;
    int irtarget=(2*n+1)*(i+1)/(2*(n-k-1)+1);
    
    int jltarget=(2*n+1)*  j  /(2*(n-k-1)+1)+1;
    int jrtarget=(2*n+1)*(j+1)/(2*(n-k-1)+1);

    char arr[45][45];
    for (int i=il0; i<=ir0; i++)
    {
        for (int j=jl0; j<=jr0; j++)
            arr[i][j]=a[0][0][(i-il0)*(jr0-jl0+1)+j-jl0];
        for (int j=jl1; j<=jr1; j++)
            arr[i][j]=a[0][1][(i-il0)*(jr1-jl1+1)+j-jl1];
        for (int j=jl2; j<=jr2; j++)
            arr[i][j]=a[0][2][(i-il0)*(jr2-jl2+1)+j-jl2];
    }
    for (int i=il1; i<=ir1; i++)
    {
        for (int j=jl0; j<=jr0; j++)
            arr[i][j]=a[1][0][(i-il1)*(jr0-jl0+1)+j-jl0];
        for (int j=jl1; j<=jr1; j++)
            arr[i][j]=a[1][1][(i-il1)*(jr1-jl1+1)+j-jl1];
        for (int j=jl2; j<=jr2; j++)
            arr[i][j]=a[1][2][(i-il1)*(jr2-jl2+1)+j-jl2];
    }
    for (int i=il2; i<=ir2; i++)
    {
        for (int j=jl0; j<=jr0; j++)
            arr[i][j]=a[2][0][(i-il2)*(jr0-jl0+1)+j-jl0];
        for (int j=jl1; j<=jr1; j++)
            arr[i][j]=a[2][1][(i-il2)*(jr1-jl1+1)+j-jl1];
        for (int j=jl2; j<=jr2; j++)
            arr[i][j]=a[2][2][(i-il2)*(jr2-jl2+1)+j-jl2];
    }
    string str;
    for (int i=iltarget; i<=irtarget; i++)
        for (int j=jltarget; j<=jrtarget; j++)
            str.push_back(arr[i][j]);
    for (int i=0; i<100-(irtarget-iltarget+1)*(jrtarget-jltarget+1); i++)
        str.push_back('0');
    if (k!=n-1)
        return str;
    a[0][0]=str;
    
    int visited[45][45], ans=0;
    for (int i=0; i<=2*n; i++)
        for (int j=0; j<=2*n; j++)
            visited[i][j]=0;
    pair<int, int> adj[4]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    queue<pair<int, int> > q;
    for (int i=0; i<=2*n; i++)
    {
        for (int j=0; j<=2*n; j++)
        {
            if (a[0][0][i*(2*n+1)+j]=='1' && !visited[i][j])
            {
                ans++;
                visited[i][j]=1;
                q.push({i, j});
                while (!q.empty())
                {
                    int ui=q.front().first, uj=q.front().second;
                    q.pop();
                    for (int l=0; l<4; l++)
                    {
                        int vi=ui+adj[l].first, vj=uj+adj[l].second;
                        if (0<=vi && vi<=2*n && 0<=vj && vj<=2*n && a[0][0][vi*(2*n+1)+vj]=='1' && !visited[vi][vj])
                        {
                            visited[vi][vj]=1;
                            q.push({vi, vj});
                        }
                    }
                }
            }
        }
    }
    for (int i=0; i<10; i++)
        a[0][0][i]='0'+(bool)(ans&(1<<i));
    for (int i=10; i<100; i++)
        a[0][0][i]='0';
    return a[0][0];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 4 ms 2100 KB Output is correct
3 Correct 7 ms 1932 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 2 ms 2216 KB Output is correct
6 Correct 4 ms 1944 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 4 ms 2100 KB Output is correct
3 Correct 7 ms 1932 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 2 ms 2216 KB Output is correct
6 Correct 4 ms 1944 KB Output is correct
7 Correct 8 ms 2172 KB Output is correct
8 Correct 8 ms 2120 KB Output is correct
9 Correct 11 ms 2096 KB Output is correct
10 Correct 9 ms 2076 KB Output is correct
11 Correct 8 ms 2176 KB Output is correct
12 Correct 8 ms 1848 KB Output is correct
13 Correct 10 ms 2028 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 4 ms 2100 KB Output is correct
3 Correct 7 ms 1932 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 2 ms 2216 KB Output is correct
6 Correct 4 ms 1944 KB Output is correct
7 Correct 8 ms 2172 KB Output is correct
8 Correct 8 ms 2120 KB Output is correct
9 Correct 11 ms 2096 KB Output is correct
10 Correct 9 ms 2076 KB Output is correct
11 Correct 8 ms 2176 KB Output is correct
12 Correct 8 ms 1848 KB Output is correct
13 Correct 10 ms 2028 KB Output is correct
14 Incorrect 3 ms 368 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 4 ms 2100 KB Output is correct
3 Correct 7 ms 1932 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 2 ms 2216 KB Output is correct
6 Correct 4 ms 1944 KB Output is correct
7 Correct 8 ms 2172 KB Output is correct
8 Correct 8 ms 2120 KB Output is correct
9 Correct 11 ms 2096 KB Output is correct
10 Correct 9 ms 2076 KB Output is correct
11 Correct 8 ms 2176 KB Output is correct
12 Correct 8 ms 1848 KB Output is correct
13 Correct 10 ms 2028 KB Output is correct
14 Incorrect 3 ms 368 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 4 ms 2100 KB Output is correct
3 Correct 7 ms 1932 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 2 ms 2216 KB Output is correct
6 Correct 4 ms 1944 KB Output is correct
7 Correct 8 ms 2172 KB Output is correct
8 Correct 8 ms 2120 KB Output is correct
9 Correct 11 ms 2096 KB Output is correct
10 Correct 9 ms 2076 KB Output is correct
11 Correct 8 ms 2176 KB Output is correct
12 Correct 8 ms 1848 KB Output is correct
13 Correct 10 ms 2028 KB Output is correct
14 Incorrect 3 ms 368 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 4 ms 2100 KB Output is correct
3 Correct 7 ms 1932 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 2 ms 2216 KB Output is correct
6 Correct 4 ms 1944 KB Output is correct
7 Correct 8 ms 2172 KB Output is correct
8 Correct 8 ms 2120 KB Output is correct
9 Correct 11 ms 2096 KB Output is correct
10 Correct 9 ms 2076 KB Output is correct
11 Correct 8 ms 2176 KB Output is correct
12 Correct 8 ms 1848 KB Output is correct
13 Correct 10 ms 2028 KB Output is correct
14 Incorrect 3 ms 368 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 4 ms 2100 KB Output is correct
3 Correct 7 ms 1932 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 2 ms 2216 KB Output is correct
6 Correct 4 ms 1944 KB Output is correct
7 Correct 8 ms 2172 KB Output is correct
8 Correct 8 ms 2120 KB Output is correct
9 Correct 11 ms 2096 KB Output is correct
10 Correct 9 ms 2076 KB Output is correct
11 Correct 8 ms 2176 KB Output is correct
12 Correct 8 ms 1848 KB Output is correct
13 Correct 10 ms 2028 KB Output is correct
14 Incorrect 3 ms 368 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 4 ms 2100 KB Output is correct
3 Correct 7 ms 1932 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 2 ms 2216 KB Output is correct
6 Correct 4 ms 1944 KB Output is correct
7 Correct 8 ms 2172 KB Output is correct
8 Correct 8 ms 2120 KB Output is correct
9 Correct 11 ms 2096 KB Output is correct
10 Correct 9 ms 2076 KB Output is correct
11 Correct 8 ms 2176 KB Output is correct
12 Correct 8 ms 1848 KB Output is correct
13 Correct 10 ms 2028 KB Output is correct
14 Incorrect 3 ms 368 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 4 ms 2100 KB Output is correct
3 Correct 7 ms 1932 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 2 ms 2216 KB Output is correct
6 Correct 4 ms 1944 KB Output is correct
7 Correct 8 ms 2172 KB Output is correct
8 Correct 8 ms 2120 KB Output is correct
9 Correct 11 ms 2096 KB Output is correct
10 Correct 9 ms 2076 KB Output is correct
11 Correct 8 ms 2176 KB Output is correct
12 Correct 8 ms 1848 KB Output is correct
13 Correct 10 ms 2028 KB Output is correct
14 Incorrect 3 ms 368 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 4 ms 2100 KB Output is correct
3 Correct 7 ms 1932 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 2 ms 2216 KB Output is correct
6 Correct 4 ms 1944 KB Output is correct
7 Correct 8 ms 2172 KB Output is correct
8 Correct 8 ms 2120 KB Output is correct
9 Correct 11 ms 2096 KB Output is correct
10 Correct 9 ms 2076 KB Output is correct
11 Correct 8 ms 2176 KB Output is correct
12 Correct 8 ms 1848 KB Output is correct
13 Correct 10 ms 2028 KB Output is correct
14 Incorrect 3 ms 368 KB invalid len
15 Halted 0 ms 0 KB -