oj.uz

답안 #1031879

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1031879 2024-07-23T08:21:36 Z vjudge1 화성 (APIO22_mars) C++17
14 / 100
 15 ms 3200 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=2*n-9;
        if(n==5) {
            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
        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<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-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==4),j+!!j*(k==4));
    }
    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;
            }
            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:128:41: warning: array subscript -1 is below array bounds of 'int [30][30][15]' [-Warray-bounds]
  128 |                 while(j>2)transport[i-=2][j-=2][CC++]=2;
      |                           ~~~~~~~~~~~~~~^
mars.cpp:109:9: note: while referencing 'transport'
  109 |     int transport[30][30][15];
      |         ^~~~~~~~~
mars.cpp:124:41: warning: array subscript -1 is below array bounds of 'int [30][30][15]' [-Warray-bounds]
  124 |                 while(j>2)transport[i-=2][j-=2][CC++]=1;
      |                           ~~~~~~~~~~~~~~^
mars.cpp:109:9: note: while referencing 'transport'
  109 |     int transport[30][30][15];
      |         ^~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2656 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 8 ms 2828 KB Output is correct
4 Correct 8 ms 3200 KB Output is correct
5 Correct 6 ms 2824 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2656 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 8 ms 2828 KB Output is correct
4 Correct 8 ms 3200 KB Output is correct
5 Correct 6 ms 2824 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2836 KB Output is correct
8 Correct 12 ms 3160 KB Output is correct
9 Correct 13 ms 2920 KB Output is correct
10 Correct 11 ms 3020 KB Output is correct
11 Correct 15 ms 3060 KB Output is correct
12 Correct 10 ms 2848 KB Output is correct
13 Correct 9 ms 3192 KB Output is correct

Subtask #3
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2656 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 8 ms 2828 KB Output is correct
4 Correct 8 ms 3200 KB Output is correct
5 Correct 6 ms 2824 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2836 KB Output is correct
8 Correct 12 ms 3160 KB Output is correct
9 Correct 13 ms 2920 KB Output is correct
10 Correct 11 ms 3020 KB Output is correct
11 Correct 15 ms 3060 KB Output is correct
12 Correct 10 ms 2848 KB Output is correct
13 Correct 9 ms 3192 KB Output is correct
14 Incorrect 2 ms 504 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2656 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 8 ms 2828 KB Output is correct
4 Correct 8 ms 3200 KB Output is correct
5 Correct 6 ms 2824 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2836 KB Output is correct
8 Correct 12 ms 3160 KB Output is correct
9 Correct 13 ms 2920 KB Output is correct
10 Correct 11 ms 3020 KB Output is correct
11 Correct 15 ms 3060 KB Output is correct
12 Correct 10 ms 2848 KB Output is correct
13 Correct 9 ms 3192 KB Output is correct
14 Incorrect 2 ms 504 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2656 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 8 ms 2828 KB Output is correct
4 Correct 8 ms 3200 KB Output is correct
5 Correct 6 ms 2824 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2836 KB Output is correct
8 Correct 12 ms 3160 KB Output is correct
9 Correct 13 ms 2920 KB Output is correct
10 Correct 11 ms 3020 KB Output is correct
11 Correct 15 ms 3060 KB Output is correct
12 Correct 10 ms 2848 KB Output is correct
13 Correct 9 ms 3192 KB Output is correct
14 Incorrect 2 ms 504 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2656 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 8 ms 2828 KB Output is correct
4 Correct 8 ms 3200 KB Output is correct
5 Correct 6 ms 2824 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2836 KB Output is correct
8 Correct 12 ms 3160 KB Output is correct
9 Correct 13 ms 2920 KB Output is correct
10 Correct 11 ms 3020 KB Output is correct
11 Correct 15 ms 3060 KB Output is correct
12 Correct 10 ms 2848 KB Output is correct
13 Correct 9 ms 3192 KB Output is correct
14 Incorrect 2 ms 504 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2656 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 8 ms 2828 KB Output is correct
4 Correct 8 ms 3200 KB Output is correct
5 Correct 6 ms 2824 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2836 KB Output is correct
8 Correct 12 ms 3160 KB Output is correct
9 Correct 13 ms 2920 KB Output is correct
10 Correct 11 ms 3020 KB Output is correct
11 Correct 15 ms 3060 KB Output is correct
12 Correct 10 ms 2848 KB Output is correct
13 Correct 9 ms 3192 KB Output is correct
14 Incorrect 2 ms 504 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2656 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 8 ms 2828 KB Output is correct
4 Correct 8 ms 3200 KB Output is correct
5 Correct 6 ms 2824 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2836 KB Output is correct
8 Correct 12 ms 3160 KB Output is correct
9 Correct 13 ms 2920 KB Output is correct
10 Correct 11 ms 3020 KB Output is correct
11 Correct 15 ms 3060 KB Output is correct
12 Correct 10 ms 2848 KB Output is correct
13 Correct 9 ms 3192 KB Output is correct
14 Incorrect 2 ms 504 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2656 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 8 ms 2828 KB Output is correct
4 Correct 8 ms 3200 KB Output is correct
5 Correct 6 ms 2824 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2836 KB Output is correct
8 Correct 12 ms 3160 KB Output is correct
9 Correct 13 ms 2920 KB Output is correct
10 Correct 11 ms 3020 KB Output is correct
11 Correct 15 ms 3060 KB Output is correct
12 Correct 10 ms 2848 KB Output is correct
13 Correct 9 ms 3192 KB Output is correct
14 Incorrect 2 ms 504 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2656 KB Output is correct
2 Correct 8 ms 2744 KB Output is correct
3 Correct 8 ms 2828 KB Output is correct
4 Correct 8 ms 3200 KB Output is correct
5 Correct 6 ms 2824 KB Output is correct
6 Correct 8 ms 2740 KB Output is correct
7 Correct 8 ms 2836 KB Output is correct
8 Correct 12 ms 3160 KB Output is correct
9 Correct 13 ms 2920 KB Output is correct
10 Correct 11 ms 3020 KB Output is correct
11 Correct 15 ms 3060 KB Output is correct
12 Correct 10 ms 2848 KB Output is correct
13 Correct 9 ms 3192 KB Output is correct
14 Incorrect 2 ms 504 KB Incorrect
15 Halted 0 ms 0 KB -