Submission #580283

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
580283	2022-06-21T03:09:20 Z	Cross_Ratio	Mars (APIO22_mars)	C++17	14 / 100	23 ms	2276 KB

mars

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-

Submission #580283

Compilation message