oj.uz

Submission #1031836

# Submission time Handle Problem Language Result Execution time Memory
1031836 2024-07-23T07:55:49 Z vjudge1 Mars (APIO22_mars) C++17
14 / 100
 13 ms 3436 KB 
#include "mars.h"
#include<bits/stdc++.h>
using namespace std;
bitset<50> grid[50];
void flod(int i,int j){
    if(i<0||i>30||j<0||j>30)return;
    if(!grid[i][j]) return;
    grid[i][j]=0;
    flod(i-1,j);
    flod(i+1,j);
    flod(i,j+1);
    flod(i,j-1);
}
string howmanyislands(int n){
    int ans=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            ans+=grid[i][j],flod(i,j);
    string str;
    for(int i=0;i<100;i++)
        str+=48+(ans&1),ans>>=1;
    return str;
}
string encode_grid(int i,int j){
    string str;
    for(int I=0;I<10;I++)
        for(int J=0;J<10;J++)
            str+=48+grid[i+I][j+J];
    return str;
}
void putintogrid(string a,int i,int j){
    int CC=0;
    for(int I=0;I<10;I++) for(int J=0;J<10;J++)
        grid[i+I][j+J]=grid[i+I][j+J]|a[CC++]=='1';
}
std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n) {
    if(n<=4) {
        for(int i=0;i<2*n+1;i++)
            grid[i].reset();
        if(i&1||j&1) return a[0][0];
        if(max(i,j)==2*n-2*k-2) {
            grid[i][j]=a[0][0][0]=='1';
            grid[i+1][j]=a[1][0][0]=='1';
            grid[i][j+1]=a[0][1][0]=='1';
            grid[i+1][j+1]=a[1][1][0]=='1';
            grid[i+2][j+1]=a[2][1][0]=='1';
            grid[i+1][j+2]=a[1][2][0]=='1';
            putintogrid(a[2][0],i+2,j);
            putintogrid(a[2][2],i+2,j+2);
            putintogrid(a[0][2],i,j+2);
        } else return a[0][0];
        if(k==n-1)
            return howmanyislands(2*n+1);
        return encode_grid(i,j);
    }
    int szofg=2*n;
    set<int> important;
    important.insert(szofg);
    important.insert(szofg-10);
    important.insert(-1);
    set<int>important2;
    important2.insert(0);
    important2.insert(szofg-8);
    if(szofg>=20)
        important2.insert(szofg-18);
    if(szofg>20)
        important.insert(szofg-20);
    if(k==n-1){
        int k=2*n-7;
        if(important2.size()==3)
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    putintogrid(a[i][j],max(0,szofg-7-(3-i)*10),max(0,szofg-7+(3-i)*10));
        else {
            putintogrid(a[0][0],0,0),putintogrid(a[2][2],k,k),putintogrid(a[2][0],k,0),putintogrid(a[0][2],0,k);
        }
        return howmanyislands(2*n+1);
    }
    if(k<4) {
        for(int i=0;i<2*n+1;i++)
            grid[i].reset();
        if(i&1||j&1) return a[0][0];
        int A=*--important.lower_bound(i);
        int B=*--important.lower_bound(j);
        if(max(i-A,j-B)==10-2*k-2||(A<0&&B<0&&max(i,j)==*++important.begin()-2*k)) {
            grid[i][j]=a[0][0][0]=='1';
            grid[i+1][j]=a[1][0][0]=='1';
            grid[i][j+1]=a[0][1][0]=='1';
            grid[i+1][j+1]=a[1][1][0]=='1';
            grid[i+2][j+1]=a[2][1][0]=='1';
            grid[i+1][j+2]=a[1][2][0]=='1';
            putintogrid(a[2][0],i+2,j);
            putintogrid(a[2][2],i+2,j+2);
            putintogrid(a[0][2],i,j+2);
        } else return a[0][0];
        return encode_grid(i+!!i*(k==3),j+!!j*(k==3));
    }
    int transport[30][30][15];
    for(auto i:important2){
        for(auto j:important2){
            int CC=4;
            int origi=i;
            int origj=j;
            if(!i){
                while(j)transport[0][j-=2][CC++]=1;
            }else if(!j) {
                while(i)transport[i-=2][0][CC++]=2;
            }else if(i==j){
                while(i)transport[i-=2][j-=2][CC++]=3;
            } else if(i<j) {
                while(i>2)transport[i-=2][j-=2][CC++]=3;
                transport[--i][j-=2][CC++]=4;
                while(j>2)transport[i-=2][j-=2][CC++]=1;
            } else {
                while(i>2)transport[i-=2][j-=2][CC++]=3;
                transport[--i][j-=2][CC++]=5;
                while(j>2)transport[i-=2][j-=2][CC++]=2;
            }
            i=origi;
            j=origj;
        }
    }
    if(i==0&&j==0)return a[0][0];
    if(transport[i][j][k]){
        if(transport[i][j][k]==1)
            return a[0][2];
        if(transport[i][j][k]==2)
            return a[2][0];
        if(transport[i][j][k]==3)
            return a[2][2];
        if(transport[i][j][k]==4)
            return a[1][2];
        if(transport[i][j][k]==5)
            return a[2][1];
        return a[0][0];
    }
    int x=max(i,j);
    if(x==1&&important2.size()==3) {
        int c=4+*++important2.begin()/2;
        if(c==k){
            return a[i][j];
        }
    }
    return a[0][0];
}

Compilation message

mars.cpp: In function 'void putintogrid(std::string, int, int)':
mars.cpp:34:46: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   34 |         grid[i+I][j+J]=grid[i+I][j+J]|a[CC++]=='1';
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:117:41: warning: array subscript -1 is below array bounds of 'int [30][30][15]' [-Warray-bounds]
  117 |                 while(j>2)transport[i-=2][j-=2][CC++]=2;
      |                           ~~~~~~~~~~~~~~^
mars.cpp:98:9: note: while referencing 'transport'
   98 |     int transport[30][30][15];
      |         ^~~~~~~~~
mars.cpp:113:41: warning: array subscript -1 is below array bounds of 'int [30][30][15]' [-Warray-bounds]
  113 |                 while(j>2)transport[i-=2][j-=2][CC++]=1;
      |                           ~~~~~~~~~~~~~~^
mars.cpp:98:9: note: while referencing 'transport'
   98 |     int transport[30][30][15];
      |         ^~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2660 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 6 ms 3008 KB Output is correct
4 Correct 8 ms 2748 KB Output is correct
5 Correct 6 ms 2676 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2660 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 6 ms 3008 KB Output is correct
4 Correct 8 ms 2748 KB Output is correct
5 Correct 6 ms 2676 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2992 KB Output is correct
8 Correct 12 ms 3344 KB Output is correct
9 Correct 13 ms 3012 KB Output is correct
10 Correct 13 ms 3152 KB Output is correct
11 Correct 11 ms 3436 KB Output is correct
12 Correct 11 ms 3256 KB Output is correct
13 Correct 11 ms 2912 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2660 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 6 ms 3008 KB Output is correct
4 Correct 8 ms 2748 KB Output is correct
5 Correct 6 ms 2676 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2992 KB Output is correct
8 Correct 12 ms 3344 KB Output is correct
9 Correct 13 ms 3012 KB Output is correct
10 Correct 13 ms 3152 KB Output is correct
11 Correct 11 ms 3436 KB Output is correct
12 Correct 11 ms 3256 KB Output is correct
13 Correct 11 ms 2912 KB Output is correct
14 Incorrect 2 ms 508 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2660 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 6 ms 3008 KB Output is correct
4 Correct 8 ms 2748 KB Output is correct
5 Correct 6 ms 2676 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2992 KB Output is correct
8 Correct 12 ms 3344 KB Output is correct
9 Correct 13 ms 3012 KB Output is correct
10 Correct 13 ms 3152 KB Output is correct
11 Correct 11 ms 3436 KB Output is correct
12 Correct 11 ms 3256 KB Output is correct
13 Correct 11 ms 2912 KB Output is correct
14 Incorrect 2 ms 508 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2660 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 6 ms 3008 KB Output is correct
4 Correct 8 ms 2748 KB Output is correct
5 Correct 6 ms 2676 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2992 KB Output is correct
8 Correct 12 ms 3344 KB Output is correct
9 Correct 13 ms 3012 KB Output is correct
10 Correct 13 ms 3152 KB Output is correct
11 Correct 11 ms 3436 KB Output is correct
12 Correct 11 ms 3256 KB Output is correct
13 Correct 11 ms 2912 KB Output is correct
14 Incorrect 2 ms 508 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2660 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 6 ms 3008 KB Output is correct
4 Correct 8 ms 2748 KB Output is correct
5 Correct 6 ms 2676 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2992 KB Output is correct
8 Correct 12 ms 3344 KB Output is correct
9 Correct 13 ms 3012 KB Output is correct
10 Correct 13 ms 3152 KB Output is correct
11 Correct 11 ms 3436 KB Output is correct
12 Correct 11 ms 3256 KB Output is correct
13 Correct 11 ms 2912 KB Output is correct
14 Incorrect 2 ms 508 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2660 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 6 ms 3008 KB Output is correct
4 Correct 8 ms 2748 KB Output is correct
5 Correct 6 ms 2676 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2992 KB Output is correct
8 Correct 12 ms 3344 KB Output is correct
9 Correct 13 ms 3012 KB Output is correct
10 Correct 13 ms 3152 KB Output is correct
11 Correct 11 ms 3436 KB Output is correct
12 Correct 11 ms 3256 KB Output is correct
13 Correct 11 ms 2912 KB Output is correct
14 Incorrect 2 ms 508 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2660 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 6 ms 3008 KB Output is correct
4 Correct 8 ms 2748 KB Output is correct
5 Correct 6 ms 2676 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2992 KB Output is correct
8 Correct 12 ms 3344 KB Output is correct
9 Correct 13 ms 3012 KB Output is correct
10 Correct 13 ms 3152 KB Output is correct
11 Correct 11 ms 3436 KB Output is correct
12 Correct 11 ms 3256 KB Output is correct
13 Correct 11 ms 2912 KB Output is correct
14 Incorrect 2 ms 508 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2660 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 6 ms 3008 KB Output is correct
4 Correct 8 ms 2748 KB Output is correct
5 Correct 6 ms 2676 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2992 KB Output is correct
8 Correct 12 ms 3344 KB Output is correct
9 Correct 13 ms 3012 KB Output is correct
10 Correct 13 ms 3152 KB Output is correct
11 Correct 11 ms 3436 KB Output is correct
12 Correct 11 ms 3256 KB Output is correct
13 Correct 11 ms 2912 KB Output is correct
14 Incorrect 2 ms 508 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2660 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 6 ms 3008 KB Output is correct
4 Correct 8 ms 2748 KB Output is correct
5 Correct 6 ms 2676 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2992 KB Output is correct
8 Correct 12 ms 3344 KB Output is correct
9 Correct 13 ms 3012 KB Output is correct
10 Correct 13 ms 3152 KB Output is correct
11 Correct 11 ms 3436 KB Output is correct
12 Correct 11 ms 3256 KB Output is correct
13 Correct 11 ms 2912 KB Output is correct
14 Incorrect 2 ms 508 KB Incorrect
15 Halted 0 ms 0 KB -