oj.uz

Submission #1031764

# Submission time Handle Problem Language Result Execution time Memory
1031764 2024-07-23T06:46:58 Z vjudge1 Mars (APIO22_mars) C++17
14 / 100
 14 ms 4044 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(0);
    important.insert(szofg);
    important.insert(szofg-10);
    set<int>important2;
    important2.insert(0);
    important2.insert(szofg-10);
    if(szofg>20)
        important2.insert(szofg-20);
    if(szofg>20)
        important.insert(szofg-20);
    if(k==n-1){
        int k=*++important2.begin();
        if(important.size()==3)
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    putintogrid(a[i][j],max(0,szofg-30+i*10),max(0,szofg-30+j*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<5) {
        for(int i=0;i<2*n+1;i++)
            grid[i].reset();
        if(i&1||j&1) return a[0][0];
        int A=*--important.upper_bound(i);
        int B=*--important.upper_bound(j);
        if(max(i-A,j-B)==10-2*k-2||(!A&&!B&&max(i,j)==*++important.begin()-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];
        return encode_grid(i,j);
    }
    int transport[30][30][15];
    for(auto i:important2){
        for(auto j:important2){
            int CC=5;
            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;
            }
        }
    }
    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:102:17: warning: unused variable 'origi' [-Wunused-variable]
  102 |             int origi=i;
      |                 ^~~~~
mars.cpp:103:17: warning: unused variable 'origj' [-Wunused-variable]
  103 |             int origj=j;
      |                 ^~~~~
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 8 ms 3484 KB Output is correct
2 Correct 10 ms 3384 KB Output is correct
3 Correct 6 ms 3520 KB Output is correct
4 Correct 7 ms 3472 KB Output is correct
5 Correct 10 ms 3296 KB Output is correct
6 Correct 9 ms 3472 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3484 KB Output is correct
2 Correct 10 ms 3384 KB Output is correct
3 Correct 6 ms 3520 KB Output is correct
4 Correct 7 ms 3472 KB Output is correct
5 Correct 10 ms 3296 KB Output is correct
6 Correct 9 ms 3472 KB Output is correct
7 Correct 10 ms 3992 KB Output is correct
8 Correct 14 ms 3704 KB Output is correct
9 Correct 12 ms 4044 KB Output is correct
10 Correct 14 ms 3548 KB Output is correct
11 Correct 12 ms 3456 KB Output is correct
12 Correct 14 ms 3596 KB Output is correct
13 Correct 13 ms 3532 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3484 KB Output is correct
2 Correct 10 ms 3384 KB Output is correct
3 Correct 6 ms 3520 KB Output is correct
4 Correct 7 ms 3472 KB Output is correct
5 Correct 10 ms 3296 KB Output is correct
6 Correct 9 ms 3472 KB Output is correct
7 Correct 10 ms 3992 KB Output is correct
8 Correct 14 ms 3704 KB Output is correct
9 Correct 12 ms 4044 KB Output is correct
10 Correct 14 ms 3548 KB Output is correct
11 Correct 12 ms 3456 KB Output is correct
12 Correct 14 ms 3596 KB Output is correct
13 Correct 13 ms 3532 KB Output is correct
14 Incorrect 3 ms 732 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3484 KB Output is correct
2 Correct 10 ms 3384 KB Output is correct
3 Correct 6 ms 3520 KB Output is correct
4 Correct 7 ms 3472 KB Output is correct
5 Correct 10 ms 3296 KB Output is correct
6 Correct 9 ms 3472 KB Output is correct
7 Correct 10 ms 3992 KB Output is correct
8 Correct 14 ms 3704 KB Output is correct
9 Correct 12 ms 4044 KB Output is correct
10 Correct 14 ms 3548 KB Output is correct
11 Correct 12 ms 3456 KB Output is correct
12 Correct 14 ms 3596 KB Output is correct
13 Correct 13 ms 3532 KB Output is correct
14 Incorrect 3 ms 732 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3484 KB Output is correct
2 Correct 10 ms 3384 KB Output is correct
3 Correct 6 ms 3520 KB Output is correct
4 Correct 7 ms 3472 KB Output is correct
5 Correct 10 ms 3296 KB Output is correct
6 Correct 9 ms 3472 KB Output is correct
7 Correct 10 ms 3992 KB Output is correct
8 Correct 14 ms 3704 KB Output is correct
9 Correct 12 ms 4044 KB Output is correct
10 Correct 14 ms 3548 KB Output is correct
11 Correct 12 ms 3456 KB Output is correct
12 Correct 14 ms 3596 KB Output is correct
13 Correct 13 ms 3532 KB Output is correct
14 Incorrect 3 ms 732 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3484 KB Output is correct
2 Correct 10 ms 3384 KB Output is correct
3 Correct 6 ms 3520 KB Output is correct
4 Correct 7 ms 3472 KB Output is correct
5 Correct 10 ms 3296 KB Output is correct
6 Correct 9 ms 3472 KB Output is correct
7 Correct 10 ms 3992 KB Output is correct
8 Correct 14 ms 3704 KB Output is correct
9 Correct 12 ms 4044 KB Output is correct
10 Correct 14 ms 3548 KB Output is correct
11 Correct 12 ms 3456 KB Output is correct
12 Correct 14 ms 3596 KB Output is correct
13 Correct 13 ms 3532 KB Output is correct
14 Incorrect 3 ms 732 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3484 KB Output is correct
2 Correct 10 ms 3384 KB Output is correct
3 Correct 6 ms 3520 KB Output is correct
4 Correct 7 ms 3472 KB Output is correct
5 Correct 10 ms 3296 KB Output is correct
6 Correct 9 ms 3472 KB Output is correct
7 Correct 10 ms 3992 KB Output is correct
8 Correct 14 ms 3704 KB Output is correct
9 Correct 12 ms 4044 KB Output is correct
10 Correct 14 ms 3548 KB Output is correct
11 Correct 12 ms 3456 KB Output is correct
12 Correct 14 ms 3596 KB Output is correct
13 Correct 13 ms 3532 KB Output is correct
14 Incorrect 3 ms 732 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3484 KB Output is correct
2 Correct 10 ms 3384 KB Output is correct
3 Correct 6 ms 3520 KB Output is correct
4 Correct 7 ms 3472 KB Output is correct
5 Correct 10 ms 3296 KB Output is correct
6 Correct 9 ms 3472 KB Output is correct
7 Correct 10 ms 3992 KB Output is correct
8 Correct 14 ms 3704 KB Output is correct
9 Correct 12 ms 4044 KB Output is correct
10 Correct 14 ms 3548 KB Output is correct
11 Correct 12 ms 3456 KB Output is correct
12 Correct 14 ms 3596 KB Output is correct
13 Correct 13 ms 3532 KB Output is correct
14 Incorrect 3 ms 732 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3484 KB Output is correct
2 Correct 10 ms 3384 KB Output is correct
3 Correct 6 ms 3520 KB Output is correct
4 Correct 7 ms 3472 KB Output is correct
5 Correct 10 ms 3296 KB Output is correct
6 Correct 9 ms 3472 KB Output is correct
7 Correct 10 ms 3992 KB Output is correct
8 Correct 14 ms 3704 KB Output is correct
9 Correct 12 ms 4044 KB Output is correct
10 Correct 14 ms 3548 KB Output is correct
11 Correct 12 ms 3456 KB Output is correct
12 Correct 14 ms 3596 KB Output is correct
13 Correct 13 ms 3532 KB Output is correct
14 Incorrect 3 ms 732 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3484 KB Output is correct
2 Correct 10 ms 3384 KB Output is correct
3 Correct 6 ms 3520 KB Output is correct
4 Correct 7 ms 3472 KB Output is correct
5 Correct 10 ms 3296 KB Output is correct
6 Correct 9 ms 3472 KB Output is correct
7 Correct 10 ms 3992 KB Output is correct
8 Correct 14 ms 3704 KB Output is correct
9 Correct 12 ms 4044 KB Output is correct
10 Correct 14 ms 3548 KB Output is correct
11 Correct 12 ms 3456 KB Output is correct
12 Correct 14 ms 3596 KB Output is correct
13 Correct 13 ms 3532 KB Output is correct
14 Incorrect 3 ms 732 KB Incorrect
15 Halted 0 ms 0 KB -