oj.uz

답안 #580283

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580283 2022-06-21T03:09:20 Z Cross_Ratio 화성 (APIO22_mars) C++17
14 / 100
 23 ms 2276 KB 
#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
string sor(string s1, string s2) {
    string s3;
    s3.resize(100);
    for(int i = 0; i < 100; i ++) {
        if(s1[i]=='1'||s2[i]=='1') s3[i] = '1';
        else s3[i] = '0';
    }
    return s3;
}
string shift(string s, int k) {
    string s2;
    s2.resize(100);
    for(int i = 0; i+k<100;i++) {
        s2[i+k] = s[i];
    }
    for(int i = 0; i < k; i++) s2[i] = '0';
    return s2;
}
int A[50][50][50];
string process(vector<vector<string>> A, int a, int b, int k, int N) {
    int i, j;
    if(N<=4) {
        if(k==0) {
            for(i=0;i<3;i++) {
                for(j=0;j<3;j++) {
                    A[i][j] = shift(A[i][j],(2*N+1)*(i+a)+(j+b));
                    //for(int m = 0; m < 9; m++) cout << A[i][j][m];
                    //cout << '\n';
                }
            }
        }

        string s3;
        s3.resize(100);
        for(int i = 0; i < 100; i++) s3[i] = '0';
        for(i=0;i<3;i++) {
            for(j=0;j<3;j++) s3 = sor(s3,A[i][j]);
        }
        /*cout <<a << ' ' << b << '\n';
        for(i=0;i<2*N+1;i++) {
            for(j=0;j<2*N+1;j++) cout << s3[(2*N+1)*i+j] << ' ';
            cout << '\n';
        }*/
        if(k!=N-1) return s3;
        int dx[4] = {0,0,1,-1};
        int dy[4] = {1,-1,0,0};
        vector<vector<bool>> vis;
        vis.resize(2*N+1);
        for(i=0;i<2*N+1;i++) vis[i].resize(2*N+1);
        for(i=0;i<2*N+1;i++) {
            for(j=0;j<2*N+1;j++) vis[i][j] = false;
        }
        int ans = 0;
        for(i=0;i<2*N+1;i++) {
            for(j=0;j<2*N+1;j++) {
                if(vis[i][j]) continue;
                if(s3[(2*N+1)*i+j]=='1') {
                    ans++;
                    queue<int> Q;
                    Q.push((2*N+1)*i+j);
                    while(!Q.empty()) {
                        int c = Q.front();
                        Q.pop();
                        vis[c/(2*N+1)][c%(2*N+1)] = true;
                        for(int m = 0; m < 4; m++) {
                            int x = c/(2*N+1)+dx[m];
                            int y = c%(2*N+1)+dy[m];
                            if(0<=x&&x<2*N+1&&0<=y&&y<2*N+1) {
                                if(!vis[x][y]&&s3[(2*N+1)*x+y]=='1') {
                                    Q.push((2*N+1)*x+y);
                                }
                            }
                        }
                    }
                }
            }
        }
        string ans_string;
        ans_string.resize(100);
        for(i=0;i<100;i++) ans_string[i] = '0';
        int id = 0;
        while(ans) {
            ans_string[id] = (char)('0'+ans%2);
            ans /= 2;
            id++;
        }
        return ans_string;
    }
    else {
        if(k==N-1) {
            int dx[4] = {0,0,1,-1};
            int dy[4] = {1,-1,0,0};
            string s3;
            s3.resize((2*N+1)*(2*N+1));
            for(i=0;i<3;i++) {
                for(j=0;j<3;j++) {
                    for(int m = 0; m < 81; m++) {
                        s3[(2*N+1)*((N-4)*i+m/9)+((N-4)*j+m%9)] = A[i][j][m];
                    }
                }
            }
            /*for(i=0;i<3;i++) {
                for(j=0;j<3;j++) {
                    for(int m = 0; m < 9; m++) {
                        for(int m2 = 0; m2 < 9; m2++) cout << A[i][j][9*m+m2] << ' ';
                        cout << '\n';
                    }
                    cout << "\n\n\n";
                }
            }*/
            cout << N << '\n';
            for(i=0;i<2*N+1;i++) {
                for(j=0;j<2*N+1;j++) cout << s3[(2*N+1)*i+j] << ' ';
                cout << '\n';
            }
            vector<vector<bool>> vis;
            vis.resize(2*N+1);
            for(i=0;i<2*N+1;i++) vis[i].resize(2*N+1);
            for(i=0;i<2*N+1;i++) {
                for(j=0;j<2*N+1;j++) vis[i][j] = false;
            }
            int ans = 0;
            for(i=0;i<2*N+1;i++) {
                for(j=0;j<2*N+1;j++) {
                    if(vis[i][j]) continue;
                    if(s3[(2*N+1)*i+j]=='1') {
                        ans++;
                        queue<int> Q;
                        Q.push((2*N+1)*i+j);
                        while(!Q.empty()) {
                            int c = Q.front();
                            Q.pop();
                            if(vis[c/(2*N+1)][c%(2*N+1)]) continue;
                            vis[c/(2*N+1)][c%(2*N+1)] = true;
                            for(int m = 0; m < 4; m++) {
                                int x = c/(2*N+1)+dx[m];
                                int y = c%(2*N+1)+dy[m];
                                if(0<=x&&x<2*N+1&&0<=y&&y<2*N+1) {
                                    if(!vis[x][y]&&s3[(2*N+1)*x+y]=='1') {
                                        Q.push((2*N+1)*x+y);
                                    }
                                }
                            }
                        }
                    }
                }
            }
            string ans_string;
            ans_string.resize(100);
            for(i=0;i<100;i++) ans_string[i] = '0';
            int id = 0;
            while(ans) {
                ans_string[id] = (char)('0'+ans%2);
                ans /= 2;
                id++;
            }
            return ans_string;
        }
        if(k < 4) {
            string s3;
            s3.resize(100);
            for(int i = 0; i < 100; i++) s3[i] = '0';
            for(i=0;i<3;i++) {
                for(j=0;j<3;j++) {
                    for(int m = 0; m < (2*k+1)*(2*k+1);m++) {
                        s3[(2*k+3)*(i+m/(2*k+1))+j+m%(2*k+1)] = A[i][j][m];
                    }
                }
            }
            /*cout << a << ' ' << b << ' ' << k << '\n';
            for(i=0;i<(2*k+3)*(2*k+3);i++) {
                cout << s3[i] << ' ';
                if(i%(2*k+3)==2*k+2) cout << '\n';
            }
            cout << '\n';*/
            return s3;
        }
        else {
            return A[a/(N-k-1)][b/(N-k-1)];
        }
        /*cout <<a << ' ' << b << '\n';
        for(i=0;i<2*N+1;i++) {
            for(j=0;j<2*N+1;j++) cout << s3[(2*N+1)*i+j] << ' ';
            cout << '\n';
        }*/

    }
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1800 KB Output is correct
2 Correct 8 ms 2068 KB Output is correct
3 Correct 8 ms 2056 KB Output is correct
4 Correct 8 ms 2084 KB Output is correct
5 Correct 8 ms 2272 KB Output is correct
6 Correct 8 ms 2100 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1800 KB Output is correct
2 Correct 8 ms 2068 KB Output is correct
3 Correct 8 ms 2056 KB Output is correct
4 Correct 8 ms 2084 KB Output is correct
5 Correct 8 ms 2272 KB Output is correct
6 Correct 8 ms 2100 KB Output is correct
7 Correct 15 ms 2064 KB Output is correct
8 Correct 20 ms 2276 KB Output is correct
9 Correct 22 ms 2076 KB Output is correct
10 Correct 23 ms 2204 KB Output is correct
11 Correct 20 ms 2188 KB Output is correct
12 Correct 23 ms 2192 KB Output is correct
13 Correct 20 ms 2212 KB Output is correct

Subtask #3
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1800 KB Output is correct
2 Correct 8 ms 2068 KB Output is correct
3 Correct 8 ms 2056 KB Output is correct
4 Correct 8 ms 2084 KB Output is correct
5 Correct 8 ms 2272 KB Output is correct
6 Correct 8 ms 2100 KB Output is correct
7 Correct 15 ms 2064 KB Output is correct
8 Correct 20 ms 2276 KB Output is correct
9 Correct 22 ms 2076 KB Output is correct
10 Correct 23 ms 2204 KB Output is correct
11 Correct 20 ms 2188 KB Output is correct
12 Correct 23 ms 2192 KB Output is correct
13 Correct 20 ms 2212 KB Output is correct
14 Incorrect 5 ms 340 KB Security violation, do not print anything to stdio
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1800 KB Output is correct
2 Correct 8 ms 2068 KB Output is correct
3 Correct 8 ms 2056 KB Output is correct
4 Correct 8 ms 2084 KB Output is correct
5 Correct 8 ms 2272 KB Output is correct
6 Correct 8 ms 2100 KB Output is correct
7 Correct 15 ms 2064 KB Output is correct
8 Correct 20 ms 2276 KB Output is correct
9 Correct 22 ms 2076 KB Output is correct
10 Correct 23 ms 2204 KB Output is correct
11 Correct 20 ms 2188 KB Output is correct
12 Correct 23 ms 2192 KB Output is correct
13 Correct 20 ms 2212 KB Output is correct
14 Incorrect 5 ms 340 KB Security violation, do not print anything to stdio
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1800 KB Output is correct
2 Correct 8 ms 2068 KB Output is correct
3 Correct 8 ms 2056 KB Output is correct
4 Correct 8 ms 2084 KB Output is correct
5 Correct 8 ms 2272 KB Output is correct
6 Correct 8 ms 2100 KB Output is correct
7 Correct 15 ms 2064 KB Output is correct
8 Correct 20 ms 2276 KB Output is correct
9 Correct 22 ms 2076 KB Output is correct
10 Correct 23 ms 2204 KB Output is correct
11 Correct 20 ms 2188 KB Output is correct
12 Correct 23 ms 2192 KB Output is correct
13 Correct 20 ms 2212 KB Output is correct
14 Incorrect 5 ms 340 KB Security violation, do not print anything to stdio
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1800 KB Output is correct
2 Correct 8 ms 2068 KB Output is correct
3 Correct 8 ms 2056 KB Output is correct
4 Correct 8 ms 2084 KB Output is correct
5 Correct 8 ms 2272 KB Output is correct
6 Correct 8 ms 2100 KB Output is correct
7 Correct 15 ms 2064 KB Output is correct
8 Correct 20 ms 2276 KB Output is correct
9 Correct 22 ms 2076 KB Output is correct
10 Correct 23 ms 2204 KB Output is correct
11 Correct 20 ms 2188 KB Output is correct
12 Correct 23 ms 2192 KB Output is correct
13 Correct 20 ms 2212 KB Output is correct
14 Incorrect 5 ms 340 KB Security violation, do not print anything to stdio
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1800 KB Output is correct
2 Correct 8 ms 2068 KB Output is correct
3 Correct 8 ms 2056 KB Output is correct
4 Correct 8 ms 2084 KB Output is correct
5 Correct 8 ms 2272 KB Output is correct
6 Correct 8 ms 2100 KB Output is correct
7 Correct 15 ms 2064 KB Output is correct
8 Correct 20 ms 2276 KB Output is correct
9 Correct 22 ms 2076 KB Output is correct
10 Correct 23 ms 2204 KB Output is correct
11 Correct 20 ms 2188 KB Output is correct
12 Correct 23 ms 2192 KB Output is correct
13 Correct 20 ms 2212 KB Output is correct
14 Incorrect 5 ms 340 KB Security violation, do not print anything to stdio
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1800 KB Output is correct
2 Correct 8 ms 2068 KB Output is correct
3 Correct 8 ms 2056 KB Output is correct
4 Correct 8 ms 2084 KB Output is correct
5 Correct 8 ms 2272 KB Output is correct
6 Correct 8 ms 2100 KB Output is correct
7 Correct 15 ms 2064 KB Output is correct
8 Correct 20 ms 2276 KB Output is correct
9 Correct 22 ms 2076 KB Output is correct
10 Correct 23 ms 2204 KB Output is correct
11 Correct 20 ms 2188 KB Output is correct
12 Correct 23 ms 2192 KB Output is correct
13 Correct 20 ms 2212 KB Output is correct
14 Incorrect 5 ms 340 KB Security violation, do not print anything to stdio
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1800 KB Output is correct
2 Correct 8 ms 2068 KB Output is correct
3 Correct 8 ms 2056 KB Output is correct
4 Correct 8 ms 2084 KB Output is correct
5 Correct 8 ms 2272 KB Output is correct
6 Correct 8 ms 2100 KB Output is correct
7 Correct 15 ms 2064 KB Output is correct
8 Correct 20 ms 2276 KB Output is correct
9 Correct 22 ms 2076 KB Output is correct
10 Correct 23 ms 2204 KB Output is correct
11 Correct 20 ms 2188 KB Output is correct
12 Correct 23 ms 2192 KB Output is correct
13 Correct 20 ms 2212 KB Output is correct
14 Incorrect 5 ms 340 KB Security violation, do not print anything to stdio
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1800 KB Output is correct
2 Correct 8 ms 2068 KB Output is correct
3 Correct 8 ms 2056 KB Output is correct
4 Correct 8 ms 2084 KB Output is correct
5 Correct 8 ms 2272 KB Output is correct
6 Correct 8 ms 2100 KB Output is correct
7 Correct 15 ms 2064 KB Output is correct
8 Correct 20 ms 2276 KB Output is correct
9 Correct 22 ms 2076 KB Output is correct
10 Correct 23 ms 2204 KB Output is correct
11 Correct 20 ms 2188 KB Output is correct
12 Correct 23 ms 2192 KB Output is correct
13 Correct 20 ms 2212 KB Output is correct
14 Incorrect 5 ms 340 KB Security violation, do not print anything to stdio
15 Halted 0 ms 0 KB -