Submission #580285

#	Time	Username	Problem	Language	Result	Execution time	Memory
580285		Cross_Ratio	Mars (APIO22_mars)	C++17	44 / 100	457 ms	3432 KiB

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();
                        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;
    }
    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 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 8 / 8
• Subtask 7: 0 / 10
• Subtask 8: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11